Paper Info
Title
Scalable Sparse Subspace Clustering By Orthogonal Matching Pursuit
Abstract
Subspace clustering methods based on l(1), l(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, l(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, l(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.
Year
DOI
Venue
2016
10.1109/CVPR.2016.425
2016 IEEE CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION (CVPR)
Field
DocType
Volume
Matching pursuit,Canopy clustering algorithm,Clustering high-dimensional data,CURE data clustering algorithm,Pattern recognition,Correlation clustering,Computer science,Regularization (mathematics),Artificial intelligence,Constrained clustering,Cluster analysis,Machine learning
Conference
2016
Issue
ISSN
Citations 
1
1063-6919
27
PageRank 
References 
Authors
0.67
15
3
Name
Order
Citations
PageRank
Chong You11328.07
Daniel P. Robinson226121.51
rene victor valqui vidal35331260.14