# Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit

arXiv: https://arxiv.org/abs/1507.01238 · HTML: https://mlsanity.com/paper/1507.01238/

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2015.

## Built on by (most cited first, 30 of 50)

- [Multi-dimensional concept discovery (MCD): A unifying framework with completeness guarantees](https://mlsanity.com/paper/2301.11911/) (2023)
- [Do Sparse Autoencoders Capture Concept Manifolds?](https://mlsanity.com/paper/2604.28119/) (2026)
- [Structured Graph Learning for Scalable Subspace Clustering: From Single-view to Multi-view](https://mlsanity.com/paper/2102.07943/) (2021)
- [Pseudo-supervised Deep Subspace Clustering](https://mlsanity.com/paper/2104.03531/) (2021)
- [Image Clustering via the Principle of Rate Reduction in the Age of Pretrained Models](https://mlsanity.com/paper/2306.05272/) (2023)
- [Towards Clustering-friendly Representations: Subspace Clustering via Graph Filtering](https://mlsanity.com/paper/2106.09874/) (2021)
- [Unsupervised Manifold Linearizing and Clustering](https://mlsanity.com/paper/2301.01805/) (2023)
- [A Simple Approach to Automated Spectral Clustering](https://mlsanity.com/paper/2107.12183/) (2021)
- [Tree Variational Autoencoders](https://mlsanity.com/paper/2306.08984/) (2023)
- [Adaptive Attribute and Structure Subspace Clustering Network](https://mlsanity.com/paper/2109.13742/) (2021)
- [Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering](https://mlsanity.com/paper/2206.05553/) (2022)
- [Exploring a Principled Framework for Deep Subspace Clustering](https://mlsanity.com/paper/2503.17288/) (2025)
- [Spectral Subspace Clustering for Attributed Graphs](https://mlsanity.com/paper/2411.11074/) (2024)
- [Structuring Sparsity: Block-Sparse Featurizers Capture Visual Concept Manifolds](https://mlsanity.com/paper/2606.25234/) (2026)
- [Sparse Subspace Clustering for Concept Discovery (SSCCD)](https://mlsanity.com/paper/2203.06043/) (2022)
- [Stabilizing Self-Consuming Diffusion Models with Latent Space Filtering](https://mlsanity.com/paper/2511.12742/) (2025)
- [Deep Double Self-Expressive Subspace Clustering](https://mlsanity.com/paper/2306.11592/) (2023)
- [Provable Data Clustering via Innovation Search](https://mlsanity.com/paper/2108.06888/) (2021)
- [Subspace Change-Point Detection via Low-Rank Matrix Factorisation](https://mlsanity.com/paper/2110.04044/) (2021)
- [Fully Linear Graph Convolutional Networks for Semi-Supervised Learning and Clustering](https://mlsanity.com/paper/2111.07942/) (2021)
- [PMSSC: Parallelizable multi-subset based self-expressive model for subspace clustering](https://mlsanity.com/paper/2111.12232/) (2021)
- [Greedier is Better: Selecting Multiple Neighbors per Iteration for Sparse Subspace Clustering](https://mlsanity.com/paper/2204.02572/) (2022)
- [Subspace-Guided Feature Reconstruction for Unsupervised Anomaly Localization](https://mlsanity.com/paper/2309.13904/) (2023)
- [Contrastive Learning Subspace for Text Clustering](https://mlsanity.com/paper/2408.14119/) (2024)
- [Subspace Clustering of Subspaces: Unifying Canonical Correlation Analysis and Subspace Clustering](https://mlsanity.com/paper/2509.18653/) (2025)
- [Beyond Linear Subspace Clustering: A Comparative Study of Nonlinear Manifold Clustering Algorithms](https://mlsanity.com/paper/2103.10656/) (2021)
- [Weighted Sparse Subspace Representation: A Unified Framework for Subspace Clustering, Constrained Clustering, and Active Learning](https://mlsanity.com/paper/2106.04330/) (2021)
- [fMBN-E: Efficient Unsupervised Network Structure Ensemble and Selection for Clustering](https://mlsanity.com/paper/2107.02071/) (2021)
- [Neural Ordinary Differential Equation Model for Evolutionary Subspace Clustering and Its Applications](https://mlsanity.com/paper/2107.10484/) (2021)
- [Adaptive Fusion Affinity Graph with Noise-free Online Low-rank Representation for Natural Image Segmentation](https://mlsanity.com/paper/2110.11685/) (2021)

## Abstract (arXiv)

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.