Mixed linear regression involves the recovery of two (or more) unknown vectors from unlabeled linear measurements; that is, where each sample comes from exactly one of the vectors, but we do not know which one. It is a classic problem, and the natural and empirically most popular approach to its solution has been the EM algorithm. As in other settings, this is prone to bad local minima; however, each iteration is very fast (alternating between guessing labels, and solving with those labels). In this paper we provide a new initialization procedure for EM, based on finding the leading two eigenvectors of an appropriate matrix. We then show that with this, a re-sampled version of the EM algorithm provably converges to the correct vectors, under natural assumptions on the sampling distribution, and with nearly optimal (unimprovable) sample complexity. This provides not only the first characterization of EM's performance, but also much lower sample complexity as compared to both standard (randomly initialized) EM, and other methods for this problem.
A quite similar problem that attracts extensive attention is subspace clustering, where the goal is to learn an unknown number of linear subspaces of varying dimensions from sample points. Putting our problem in this setting, each sample @math is a vector in @math ; the points from @math correspond to one @math -dimensional subspace, and from @math to another @math -dimensional subspace. Note that this makes for a very hard instance of subspace clustering, as not only are the dimensions of each subspace very high (only one less than ambient), but the projections of the points in the first @math coordinates are exactly the same. Even without the latter restriction, one typical method @cite_4 , @cite_7 -- as an example -- requires @math to have unique solution.
@cite_4 @cite_7
2165964979 2952285266
We propose an algebraic geometric approach to the problem of estimating a mixture of linear subspaces from sample data points, the so-called generalized principal component analysis (GPCA) problem. In the absence of noise, we show that GPCA is equivalent to factoring a homogeneous polynomial whose degree is the number of subspaces and whose factors (roots) represent normal vectors to each subspace. We derive a formula for the number of subspaces n and provide an analytic solution to the factorization problem using linear algebraic techniques. The solution is closed form if and only if n spl les 4. In the presence of noise, we cast GPCA as a constrained nonlinear least squares problem and derive an optimal function from which the subspaces can be directly recovered using standard nonlinear optimization techniques. We apply GPCA to the motion segmentation problem in computer vision, i.e. the problem of estimating a mixture of motion models from 2D imagery. In many real-world problems, we are dealing with collections of high-dimensional data, such as images, videos, text and web documents, DNA microarray data, and more. Often, high-dimensional data lie close to low-dimensional structures corresponding to several classes or categories the data belongs to. In this paper, we propose and study an algorithm, called Sparse Subspace Clustering (SSC), to cluster data points that lie in a union of low-dimensional subspaces. The key idea is that, among infinitely many possible representations of a data point in terms of other points, a sparse representation corresponds to selecting a few points from the same subspace. This motivates solving a sparse optimization program whose solution is used in a spectral clustering framework to infer the clustering of data into subspaces. Since solving the sparse optimization program is in general NP-hard, we consider a convex relaxation and show that, under appropriate conditions on the arrangement of subspaces and the distribution of data, the proposed minimization program succeeds in recovering the desired sparse representations. The proposed algorithm can be solved efficiently and can handle data points near the intersections of subspaces. Another key advantage of the proposed algorithm with respect to the state of the art is that it can deal with data nuisances, such as noise, sparse outlying entries, and missing entries, directly by incorporating the model of the data into the sparse optimization program. We demonstrate the effectiveness of the proposed algorithm through experiments on synthetic data as well as the two real-world problems of motion segmentation and face clustering.