Fast recovery from a union of subspaces
We address the problem of recovering a high-dimensional but structured vector from linear observations in a general setting where the vector can come from an arbitrary union of subspaces. This setup includes well-studied problems such as compressive sensing and low-rank matrix recovery. We show how to design more efficient algorithms for the union-of subspace recovery problem by using *approximate* projections. Instantiating our general framework for the low-rank matrix recovery problem gives the fastest provable running time for an algorithm with optimal sample complexity. Moreover, we give fast approximate projections for 2D histograms, another well-studied low-dimensional model of data. We complement our theoretical results with experiments demonstrating that our framework also leads to improved time and sample complexity empirically.
Code (0)
등록된 구현이 없습니다.
Tasks
Compressive SensingSimilar Papers 제목 키워드 기반
Greedy Feature Selection for Subspace Clustering
Unions of subspaces provide a powerful generalization to linear subspace models for collections of high-dimensional data. To learn a union of subspaces from a collection of data, sets of signals in the collection that be…
Clusteringfeature selectionRobust Subspace Recovery via Bi-Sparsity Pursuit
Successful applications of sparse models in computer vision and machine learning imply that in many real-world applications, high dimensional data is distributed in a union of low dimensional subspaces. Nevertheless, the…
BIG-bench Machine LearningConvergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering
The K-subspaces (KSS) method is a generalization of the K-means method for subspace clustering. In this work, we present local convergence analysis and a recovery guarantee for KSS, assuming data are generated by the sem…
ClusteringNonlinear matrix recovery using optimization on the Grassmann manifold
We investigate the problem of recovering a partially observed high-rank matrix whose columns obey a nonlinear structure such as a union of subspaces, an algebraic variety or grouped in clusters. The recovery problem is f…
Riemannian optimizationSecond-order methodsInformation-theoretic Bounds on Matrix Completion under Union of Subspaces Model
In this short note we extend some of the recent results on matrix completion under the assumption that the columns of the matrix can be grouped (clustered) into subspaces (not necessarily disjoint or independent). This m…
ClusteringMatrix Completion