Greedy Subspace Clustering

Abstract

We consider the problem of subspace clustering: given points that lie on or near the union of many low-dimensional linear subspaces, recover the subspaces. To this end, one first identifies sets of points close to the same subspace and uses the sets to estimate the subspaces. As the geometric structure of the clusters (linear subspaces) forbids proper performance of general distance based approaches such as K-means, many model-specific methods have been proposed. In this paper, we provide new simple and efficient algorithms for this problem. Our statistical analysis shows that the algorithms are guaranteed exact (perfect) clustering performance under certain conditions on the number of points and the affinity between subspaces. These conditions are weaker than those considered in the standard statistical literature. Experimental results on synthetic data generated from the standard unions of subspaces model demonstrate our theory. We also show that our algorithm performs competitively against state-of-the-art algorithms on real-world applications such as motion segmentation and face clustering, with much simpler implementation and lower computational cost.

To appear in NIPS 2014

References in corpus (2)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• A geometric analysis of subspace clustering with outliers

Cited by in corpus (20)

• Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework
• Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
• ${\ell }_0$-Motivated Low-Rank Sparse Subspace Clustering
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Innovation Pursuit: A New Approach to Subspace Clustering
• On Geometric Analysis of Affine Sparse Subspace Clustering
• Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
• Active Orthogonal Matching Pursuit for Sparse Subspace Clustering
• Subspace clustering without knowing the number of clusters: A parameter free approach
• Evolutionary Self-Expressive Models for Subspace Clustering
• Subspace Clustering via Optimal Direction Search
• Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search
• Subspace Clustering using Ensembles of $K$-Subspaces
• Subspace-Sparse Representation
• Real-time Prediction of Soft Tissue Deformations Using Data-driven Nonlinear Presurgical Simulations
• On deterministic conditions for subspace clustering under missing data
• Outlier Detection and Data Clustering via Innovation Search
• Canonical Divergence Analysis
• Learning a mixture of two subspaces over finite fields
• Three-Stage Subspace Clustering Framework with Graph-Based Transformation and Optimization