# Greedy Subspace Clustering

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2014.

## Built on by (most cited first, 10 of 10)

- [Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering](https://mlsanity.com/paper/2206.05553/) (2022)
- [Large sample spectral analysis of graph-based multi-manifold clustering](https://mlsanity.com/paper/2107.13610/) (2021)
- [Diffusion Models Are Statistically Optimal for Learning Low-Dimensional Multi-Modal Distributions](https://mlsanity.com/paper/2605.30153/) (2026)
- [Detecting adversaries in Crowdsourcing](https://mlsanity.com/paper/2110.04117/) (2021)
- [Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search](https://mlsanity.com/paper/2106.12190/) (2021)
- [Provable Clustering of a Union of Linear Manifolds Using Optimal Directions](https://mlsanity.com/paper/2201.02745/) (2022)
- [Fusion Subspace Clustering for Incomplete Data](https://mlsanity.com/paper/2205.10872/) (2022)
- [Noisy ℓ0-Sparse Subspace Clustering on Dimensionality Reduced Data](https://mlsanity.com/paper/2206.11079/) (2022)
- [Subspace Clustering in Wavelet Packets Domain](https://mlsanity.com/paper/2406.03819/) (2024)
- [Label-independent hyperparameter-free self-supervised single-view deep subspace clustering](https://mlsanity.com/paper/2504.18179/) (2025)

## Abstract (arXiv)

We consider the problem of subspace clustering: given points that lie on or near the union of many low-dimensional linear subspaces, recover the subspaces. To this end, one first identifies sets of points close to the same subspace and uses the sets to estimate the subspaces. As the geometric structure of the clusters (linear subspaces) forbids proper performance of general distance based approaches such as K-means, many model-specific methods have been proposed. In this paper, we provide new simple and efficient algorithms for this problem. Our statistical analysis shows that the algorithms are guaranteed exact (perfect) clustering performance under certain conditions on the number of points and the affinity between subspaces. These conditions are weaker than those considered in the standard statistical literature. Experimental results on synthetic data generated from the standard unions of subspaces model demonstrate our theory. We also show that our algorithm performs competitively against state-of-the-art algorithms on real-world applications such as motion segmentation and face clustering, with much simpler implementation and lower computational cost.