Robust subspace clustering
arXiv:1301.2603 · doi:10.1214/13-AOS1199
Abstract
Subspace clustering refers to the task of finding a multi-subspace representation that best fits a collection of points taken from a high-dimensional space. This paper introduces an algorithm inspired by sparse subspace clustering (SSC) [In IEEE Conference on Computer Vision and Pattern Recognition, CVPR (2009) 2790-2797] to cluster noisy data, and develops some novel theory demonstrating its correctness. In particular, the theory uses ideas from geometric functional analysis to show that the algorithm can accurately recover the underlying subspaces under minimal requirements on their orientation, and on the number of samples per subspace. Synthetic as well as real data experiments complement our theoretical study, illustrating our approach and demonstrating its effectiveness.
arXiv commentPublished in at http://dx.doi.org/10.1214/13-AOS1199 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)
References in corpus (16)
- Robust Recovery of Subspace Structures by Low-Rank Representation
- High-dimensional graphs and variable selection with the Lasso
- The dynamics of message passing on dense graphs, with applications to compressed sensing
- Templates for Convex Cone Problems with Applications to Sparse Signal Recovery
- Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
- High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
- A geometric analysis of subspace clustering with outliers
- L1-Penalization for Mixture Regression Models
- Sparse recovery under matrix uncertainty
- Median K-flats for hybrid linear modeling with many outliers
- Hybrid Linear Modeling via Local Best-fit Flats
- Spectral clustering based on local linear approximations
- High-Rank Matrix Completion and Subspace Clustering with Missing Data
- Robust recovery of multiple subspaces by geometric l_p minimization
- Foundations of a Multi-way Spectral Clustering Framework for Hybrid Linear Modeling
- Guess Who Rated This Movie: Identifying Users Through Subspace Clustering
Cited by in corpus (18)
- Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework
- Robust Subspace Clustering with Compressed Data
- Exactly Robust Kernel Principal Component Analysis
- Subspace-Orbit Randomized Decomposition for Low-rank Matrix Approximation
- Algebraic Clustering of Affine Subspaces
- Noisy Matrix Completion under Sparse Factor Models
- Scalable and Robust Sparse Subspace Clustering Using Randomized Clustering and Multilayer Graphs
- Efficient Solvers for Sparse Subspace Clustering
- On Geometric Analysis of Affine Sparse Subspace Clustering
- Learning the nonlinear geometry of high-dimensional data: Models and algorithms
- Noisy subspace clustering via matching pursuits
- Robust Alignment for Panoramic Stitching via an Exact Rank Constraint
- Evolutionary Self-Expressive Models for Subspace Clustering
- Discriminative Transformation Learning for Fuzzy Sparse Subspace Clustering
- Beyond Linear Subspace Clustering: A Comparative Study of Nonlinear Manifold Clustering Algorithms
- Robust nonparametric nearest neighbor random process clustering
- Nonparametric Nearest Neighbor Random Process Clustering
- Clustering as Approximation by Constrained Projectors: Theory and Guarantees