Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit

By Chong You, Daniel P. Robinson, René Vidal. Computer Vision and Pattern Recognition, 2015

379 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/e767a107df5d559152912b663b196b009d67f000

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

1. Zhouchen Lin
2. Canyi Lu
3. Jiashi Feng
4. Shuicheng Yan
5. Heng Huang
6. Hongdong Li
7. Tao Mei
8. Weidong (Tom) Cai

In Computer Vision and Pattern Recognition

1. Dacheng Tao
2. Luc Van Gool
3. Jiashi Feng
4. Yi Yang
5. Shuicheng Yan
6. Ming-Hsuan Yang
7. Xiaogang Wang
8. Trevor Darrell

In Signal Processing

1. Zhouchen Lin
2. Shuicheng Yan
3. Tao Mei
4. Xiao Fu
5. Cheng Deng
6. Ian David Reid
7. Zhiyuan Dang
8. Heng Huang

Citations in the corpus

• Multi-Scale Fusion Subspace Clustering Using Similarity Constraint (2020, methodology): “…ing (LRSC) [34], Sparse Subspace Clustering (SSC) [5], Kernel Sparse Subspace Clustering (KSSC) [30], SSC by Orthogonal Matching Pursuit (SSC-OMP) [41], Efficient Dense Subspace Clustering (EDSC) [12], SSC with the pre-trained convolutional auto-encoder features (AE+SSC), EDSC with the pre-trained…”
• Deep Subspace Clustering Networks (2017, methodology): “We compare our methods against the following baselines: Low Rank Representation (LRR) [23], Low Rank Subspace Clustering (LRSC) [43], Sparse Subspace Clustering (SSC) [10], Kernel Sparse Subspace Clustering (KSSC) [35], SSC by Orthogonal Matching Pursuit (SSCOMP) [53], Efficient Dense Subspace Clust”
• Deep Clustering via Joint Convolutional Autoencoder Embedding and Relative Entropy Minimization (2017, background): “ed into different perspectives, such as hierarchical [9, 48, 60, 61], centroid-based [19, 2, 5, 3], graph-based [37, 24, 45], sequential (temporal) [11, 35, 34, 64, 33] and subspace clustering models [1, 10, 58, 58]. In another sense, they are generally divided into two subcategories, generative and”
• Towards K-means-friendly Spaces: Simultaneous Deep Learning and Clustering (2016, methodology): “Our idea is simple: SSC-OMP is essentially a procedure of constructing a similarity matrix of the data; after obtaining this matrix, it performs K-means on the rows of a matrix comprising several selected eigenvectors of the similarity matrix (Ng et al., 2002).”
• Structured Graph Learning for Scalable Subspace Clustering: From Single View to Multiview (2021, neutral): “For instance, SSCOMP [28] is built on orthogonal matching pursuit; ESSC [29] is a proximal gradient framework to solve sparse subspace clustering; ALRR [30] is a faster solver for low-rank representation.”
• Subspace Clustering by Block Diagonal Representation (2018, background): “other subspaces assumptions are proposed to analyze the block diagonal property in different settings [6], [7], [10], [34].”
• Large-scale Multi-view Subspace Clustering in Linear Time (2019, methodology): “Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit (SSCOMP) : one of the representative large-scale subspace clustering method developed in (You, Robinson, and Vidal 2016).”