The DOI matches its Crossref record; 53 of the 53 references it cites were found in a registry or an index.
Sparse Subspace Clustering: Algorithm, Theory, and Applications
Abstract
Many real-world problems deal with collections of high-dimensional data, such as images, videos, text, and web documents, DNA microarray data, and more. Often, such high-dimensional data lie close to low-dimensional structures corresponding to several classes or categories to which the data belong. In this paper, we propose and study an algorithm, called sparse subspace clustering, to cluster data points that lie in a union of low-dimensional subspaces. The key idea is that, among the infinitely many possible representations of a data point in terms of other points, a sparse representation corresponds to selecting a few points from the same subspace. This motivates solving a sparse optimization program whose solution is used in a spectral clustering framework to infer the clustering of the data into subspaces. Since solving the sparse optimization program is in general NP-hard, we consider a convex relaxation and show that, under appropriate conditions on the arrangement of the subspaces and the distribution of the data, the proposed minimization program succeeds in recovering the desired sparse representations. The proposed algorithm is efficient and can handle data points near the intersections of subspaces. Another key advantage of the proposed algorithm with respect to the state of the art is that it can deal directly with data nuisances, such as noise, sparse outlying entries, and missing entries, by incorporating the model of the data into the sparse optimization program. We demonstrate the effectiveness of the proposed algorithm through experiments on synthetic data as well as the two real-world problems of motion segmentation and face clustering.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Regression shrinkage and selection via the lasso
Tibshirani, R. (1996) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1996.tb02080.x · Cited by 51,482
Fischler, M. A., & Bolles, R. C. (1981) · Communications of the ACM · doi:10.1145/358669.358692 · Cited by 25,893
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
Bellman, R. E. (2010) · doi:10.1515/9781400835386 · Cited by 14,588
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
A tutorial on spectral clustering
von Luxburg, U. (2007) · Statistics and Computing · doi:10.1007/s11222-007-9033-z · Cited by 10,349
Robust Face Recognition via Sparse Representation
Wright, J., Yang, A. Y., Ganesh, A., Sastry, S. S., & Ma, Y. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.79 · Cited by 9,388
On Spectral Clustering: Analysis and an algorithm
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001) · Cited by 8,159
Decoding by Linear Programming
Candes, E. J., & Tao, T. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.858979 · Cited by 7,121
Robust principal component analysis?
Candès, E. J., Li, X., Ma, Y., & Wright, J. (2011) · Journal of the ACM · doi:10.1145/1970392.1970395 · Cited by 6,921
Exact Matrix Completion via Convex Optimization
Candès, E. J., & Recht, B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-009-9045-5 · Cited by 4,877
Robust Recovery of Subspace Structures by Low-Rank Representation
Liu, G., Lin, Z., Yan, S., Sun, J., Yu, Y., & Ma, Y. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.88 · Cited by 3,594
Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
Recht, B., Fazel, M., & Parrilo, P. A. (2010) · SIAM Review · doi:10.1137/070697835 · Cited by 3,471
Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
Donoho, D. L., & Elad, M. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0437847100 · Cited by 2,898
Shape and motion from image streams under orthography: a factorization method
Tomasi, C., & Kanade, T. (1992) · International Journal of Computer Vision · doi:10.1007/bf00129684 · Cited by 2,878
A dual algorithm for the solution of nonlinear variational problems via finite element approximation
Gabay, D., & Mercier, B. (1976) · Computers & Mathematics with Applications · doi:10.1016/0898-1221(76)90003-1 · Cited by 2,514
Donoho, D. L. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20132 · Cited by 2,490
Acquiring linear subspaces for face recognition under variable lighting
Lee, K.-C., Ho, J., & Kriegman, D. J. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.92 · Cited by 2,391
An Interior-Point Method for Large-Scale -Regularized Least Squares
Kim, S.-J., Koh, K., Lustig, M., Boyd, S., & Gorinevsky, D. (2007) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.910971 · Cited by 2,083
Mixtures of Probabilistic Principal Component Analyzers
Tipping, M. E., & Bishop, C. M. (1999) · Neural Computation · doi:10.1162/089976699300016728 · Cited by 1,873
Lambertian reflectance and linear subspaces
Basri, R., & Jacobs, D. W. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1177153 · Cited by 1,576
Robust Subspace Segmentation by Low-Rank Representation
Liu, G., Lin, Z., & Yu, Y. H. (2010) · Cited by 1,534
Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
Eldar, Y. C., Kuppinger, P., & Bolcskei, H. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2044837 · Cited by 1,313
Elhamifar, E., & Vidal, R. (2009) · 2009 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2009.5206547 · Cited by 1,243
Self-citationVidal, R. (2011) · IEEE Signal Processing Magazine · doi:10.1109/msp.2010.939739 · Cited by 1,126
Self-citationRobust Recovery of Signals From a Structured Union of Subspaces
Eldar, Y. C., & Mishali, M. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2030471 · Cited by 1,044
Generalized principal component analysis (GPCA)
Vidal, R., Ma, Y., & Sastry, S. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.244 · Cited by 1,038
Self-citationSparse representations in unions of bases
Gribonval, R., & Nielsen, M. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2003.820031 · Cited by 960
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
Amaldi, E., & Kann, V. (1998) · Theoretical Computer Science · doi:10.1016/s0304-3975(97)00115-1 · Cited by 753
Object Segmentation by Long Term Analysis of Point Trajectories
Brox, T., & Malik, J. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-15555-0_21 · Cited by 744
Algorithms for simultaneous sparse approximation. Part II: Convex relaxation
Tropp, J. A. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.031 · Cited by 691
Latent Low-Rank Representation for subspace segmentation and feature extraction
Liu, G., & Yan, S. (2011) · 2011 International Conference on Computer Vision · doi:10.1109/iccv.2011.6126422 · Cited by 679
A Multibody Factorization Method for Independently Moving Objects
Costeira, J. P., & Kanade, T. (1998) · International Journal of Computer Vision · doi:10.1023/a:1008000628999 · Cited by 661
A Benchmark for the Comparison of 3-D Motion Segmentation Algorithms
Tron, R., & Vidal, R. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.382974 · Cited by 658
Self-citationClustering appearances of objects under varying illumination conditions
Ho, J., Yang, M.-H., Lim, J., Lee, K.-C., & Kriegman, D. (2003) · 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings. · doi:10.1109/cvpr.2003.1211332 · Cited by 521
Unsupervised segmentation of natural images via lossy data compression
Yang, A. Y., Wright, J., Ma, Y., & Sastry, S. S. (2008) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2007.07.005 · Cited by 509
Yan, J., & Pollefeys, M. (2006) · Lecture Notes in Computer Science · doi:10.1007/11744085_8 · Cited by 489
Structured Variable Selection with Sparsity-Inducing Norms
Jenatton, R., Audibert, J.-Y., & Bach, F. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0904.3523 · Cited by 431
A geometric analysis of subspace clustering with outliers
Soltanolkotabi, M., & Candés, E. J. (2012) · The Annals of Statistics · doi:10.1214/12-aos1034 · Cited by 411
See all by looking at a few: Sparse modeling for finding representative objects
Elhamifar, E., Sapiro, G., & Vidal, R. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6247852 · Cited by 394
Self-citationMotion segmentation by subspace separation and model selection
Kanatani, K. (2002) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2001.937679 · Cited by 349
Theoretical and Empirical Results for Recovery From Multiple Measurements
van den Berg, E., & Friedlander, M. P. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2043876 · Cited by 264
Estimation of Subspace Arrangements with Applications in Modeling and Segmenting Mixed Data
Ma, Y., Yang, A. Y., Derksen, H., & Fossum, R. (2008) · SIAM Review · doi:10.1137/060655523 · Cited by 251
Recovering Sparse Signals Using Sparse Measurement Matrices in Compressed DNA Microarrays
Parvaresh, F., Vikalo, H., Misra, S., & Hassibi, B. (2008) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2008.924384 · Cited by 219
Multiscale Hybrid Linear Models for Lossy Image Representation
Hong, W., Wright, J., Huang, K., & Ma, Y. (2006) · IEEE Transactions on Image Processing · doi:10.1109/tip.2006.882016 · Cited by 195
Segmenting Motions of Different Types by Unsupervised Manifold Clustering
Goh, A., & Vidal, R. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383235 · Cited by 194
Self-citationMotion segmentation with missing data using powerfactorization and GPCA
Vidal, R., & Hartley, R. (2004) · Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004. · doi:10.1109/cvpr.2004.1315180 · Cited by 176
Self-citationMedian K-Flats for hybrid linear modeling with many outliers
Zhang, T. L., Szlam, A. D., & Lerman, G. (2009) · IEEE International Conference on Computer Vision Workshops · doi:10.1109/iccvw.2009.5457695 · Cited by 158
Block-Sparse Recovery via Convex Optimization
Elhamifar, E., & Vidal, R. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2196694 · Cited by 156
Self-citationHybrid Linear Modeling via Local Best-fit FlatsPreprint
Zhang, T., Szlam, A. D., Wang, Y., & Lerman, G. (2010) · Cited by 146
Doubly Stochastic Normalization for Spectral Clustering
Zass, R., & Shashua, A. (2007) · The MIT Press eBooks · doi:10.7551/mitpress/7503.003.0201 · Cited by 121
Geometric Structure of Degeneracy for Multi-body Motion Segmentation
Sugaya, Y., & Kanatani, K. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30212-4_2 · Cited by 89
Cited by
iCaRL: Incremental Classifier and Representation Learning
Rebuffi, S.-A., Kolesnikov, A., Sperl, G., & Lampert, C. H. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.587 · Cited by 3,988
Generalized Latent Multi-View Subspace Clustering
Zhang, C., Fu, H., Hu, Q., Cao, X., Xie, Y., Tao, D., & Xu, D. (2020) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2018.2877660 · Cited by 739
Going deeper into action recognition: A survey
Herath, S., Harandi, M., & Porikli, F. (2017) · Image and Vision Computing · doi:10.1016/j.imavis.2017.01.010 · Cited by 634
Zero-Shot Learning via Semantic Similarity Embedding
Zhang, Z., & Saligrama, V. (2015) · 2015 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2015.474 · Cited by 629
Multi-view Subspace Clustering
Gao, H., Nie, F., Li, X., & Huang, H. (2015) · 2015 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2015.482 · Cited by 614
Metadata
- Authors
- Elhamifar, E., & Vidal, R.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2013-11
- Volume
- 35
- Issue
- 11
- Pages
- 2765-2781
- ISSN
- 0162-8828 (ISSN-L)
- 2160-9292
- OpenAlex
- W1993962865
- Cited by
- 3,106
- References
- 53
- FWCI
- 196.93
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.