Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit
Authors:
- Chong YouCYChong You
- Daniel P. RobinsonDRDaniel P. Robinson
- Rene VidalRVRene Vidal
- 1 June 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 3918-3927
Abstract
Subspace clustering methods based on ℓ1, ℓ2 or nuclear norm regularization have become very popular due to their simplicity, theoretical guarantees and empirical success. However, the choice of the regularizer can greatly impact both theory and practice. For instance, ℓ1 regularization is guaranteed to give a subspace-preserving affinity (i.e., there are no connections between points from different subspaces) under broad conditions (e.g., arbitrary subspaces and corrupted data). However, it requires solving a large scale convex optimization problem. On the other hand, ℓ2 and nuclear norm regularization provide efficient closed form solutions, but require very strong assumptions to guarantee a subspace-preserving affinity, e.g., independent subspaces and uncorrupted data. In this paper we study a subspace clustering method based on orthogonal matching pursuit. We show that the method is both computationally efficient and guaranteed to give a subspace-preserving affinity under broad conditions. Experiments on synthetic data verify our theoretical analysis, and applications in handwritten digit and face clustering show that our approach achieves the best trade off between accuracy and efficiency. Moreover, our approach is the first one to handle 100,000 data points.Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Low rank subspace clustering (LRSC)Pattern Recognition Letters, 2014
- Hybrid Linear Modeling via Local Best-Fit FlatsInternational Journal of Computer Vision, 2012
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and ImagesSIAM Review, 2009
- Spectral Curvature Clustering (SCC)International Journal of Computer Vision, 2008
- Multiframe Motion Segmentation with Missing Data Using PowerFactorization and GPCAInternational Journal of Computer Vision, 2007
- A tutorial on spectral clusteringStatistics and Computing, 2007
- Greed is Good: Algorithmic Results for Sparse ApproximationIEEE Transactions on Information Theory, 2004
- Lambertian reflectance and linear subspacesIEEE Transactions on Pattern Analysis and Machine Intelligence, 2003
- From few to many: illumination cone models for face recognition under variable lighting and poseIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- Gradient-based learning applied to document recognitionProceedings of the IEEE, 1998