Robust subspace clustering

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.

Published 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 (6)

• 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
• High-Rank Matrix Completion and Subspace Clustering with Missing Data
• 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