mlsanityData to 7 Oct 2026

Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit

arXiv 1507.01238 ↗First posted 5 Jul 2015cs.CV cs.LG stat.MLcited by 50

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 15; 2022: 14; 2023: 9; 2024: 2; 2025: 6; 2026: 4.

50 papers.

Sort:

By area:

  1. 2023Multi-dimensional concept discovery (MCD): A unifying framework with completeness guaranteescited by 48
  2. 2021Structured Graph Learning for Scalable Subspace Clustering: From Single-view to Multi-viewcited by 30
  3. 2021Pseudo-supervised Deep Subspace Clusteringcited by 29
  4. 2026Do Sparse Autoencoders Capture Concept Manifolds?cited by 25
  5. 2023Image Clustering via the Principle of Rate Reduction in the Age of Pretrained Modelscited by 22
  6. 2021Towards Clustering-friendly Representations: Subspace Clustering via Graph Filteringcited by 14
  7. 2023Unsupervised Manifold Linearizing and Clusteringcited by 12
  8. 2021A Simple Approach to Automated Spectral Clusteringcited by 10
  9. 2023Tree Variational Autoencoderscited by 10
  10. 2021Adaptive Attribute and Structure Subspace Clustering Networkcited by 9
  11. 2022Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clusteringcited by 9
  12. 2025Exploring a Principled Framework for Deep Subspace Clusteringcited by 7
38 more
  1. 2024Spectral Subspace Clustering for Attributed Graphscited by 6
  2. 2022Sparse Subspace Clustering for Concept Discovery (SSCCD)cited by 4
  3. 2023Deep Double Self-Expressive Subspace Clusteringcited by 3
  4. 2025Stabilizing Self-Consuming Diffusion Models with Latent Space Filteringcited by 3
  5. 2026Structuring Sparsity: Block-Sparse Featurizers Capture Visual Concept Manifoldscited by 3
  6. 2021Provable Data Clustering via Innovation Searchcited by 1
  7. 2021Subspace Change-Point Detection via Low-Rank Matrix Factorisationcited by 1
  8. 2021Fully Linear Graph Convolutional Networks for Semi-Supervised Learning and Clusteringcited by 1
  9. 2021PMSSC: Parallelizable multi-subset based self-expressive model for subspace clusteringcited by 1
  10. 2022Greedier is Better: Selecting Multiple Neighbors per Iteration for Sparse Subspace Clusteringcited by 1
  11. 2023Subspace-Guided Feature Reconstruction for Unsupervised Anomaly Localizationcited by 1
  12. 2024Contrastive Learning Subspace for Text Clusteringcited by 1
  13. 2025Subspace Clustering of Subspaces: Unifying Canonical Correlation Analysis and Subspace Clusteringcited by 1
  14. 2021Beyond Linear Subspace Clustering: A Comparative Study of Nonlinear Manifold Clustering Algorithmscited by 0
  15. 2021Weighted Sparse Subspace Representation: A Unified Framework for Subspace Clustering, Constrained Clustering, and Active Learningcited by 0
  16. 2021fMBN-E: Efficient Unsupervised Network Structure Ensemble and Selection for Clusteringcited by 0
  17. 2021Neural Ordinary Differential Equation Model for Evolutionary Subspace Clustering and Its Applicationscited by 0
  18. 2021Adaptive Fusion Affinity Graph with Noise-free Online Low-rank Representation for Natural Image Segmentationcited by 0
  19. 2021Learning Deep Representation with Energy-Based Self-Expressiveness for Subspace Clusteringcited by 0
  20. 2022Provable Clustering of a Union of Linear Manifolds Using Optimal Directionscited by 0
  21. 2022Dictionary learning for clustering on hyperspectral imagescited by 0
  22. 2022Fusion Subspace Clustering for Incomplete Datacited by 0
  23. 2022Self-Supervised Deep Subspace Clustering with Entropy-normcited by 0
  24. 2022Noisy ℓ0-Sparse Subspace Clustering on Dimensionality Reduced Datacited by 0
  25. 2022Revisiting data augmentation for subspace clusteringcited by 0
  26. 2022Sparse Optimization for Unsupervised Extractive Summarization of Long Documents with the Frank-Wolfe Algorithmcited by 0
  27. 2022Local and Global Structure Preservation Based Spectral Clusteringcited by 0
  28. 2022Inv-SENnet: Invariant Self Expression Network for clustering under biased datacited by 0
  29. 2022Simple and Scalable Algorithms for Cluster-Aware Precision Medicinecited by 0
  30. 2022Variable Clustering via Distributionally Robust Nodewise Regressioncited by 0
  31. 2023One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clusteringcited by 0
  32. 2023Learning Structure Aware Deep Spectral Embeddingcited by 0
  33. 2023Robust Data Clustering with Outliers via Transformed Tensor Low-Rank Representationcited by 0
  34. 2025Masked Subspace Clustering Methodscited by 0
  35. 2025Optimal Graph Clustering without Edge Density Signalscited by 0
  36. 2025Scalable Deep Subspace Clustering Networkcited by 0
  37. 2026Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesycited by 0
  38. 2026VLM4Cluster: Benchmarking Deep Clustering In the Era of Vision-Language Pre-trainingcited by 0