# Robust Subspace Clustering via Thresholding

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jul 2013.

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

- [Image Clustering via the Principle of Rate Reduction in the Age of Pretrained Models](https://mlsanity.com/paper/2306.05272/) (2023)
- [Unsupervised Manifold Linearizing and Clustering](https://mlsanity.com/paper/2301.01805/) (2023)
- [Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering](https://mlsanity.com/paper/2206.05553/) (2022)
- [Mitigating exponential concentration in covariant quantum kernels for subspace and real-world data](https://mlsanity.com/paper/2412.07915/) (2024)
- [Diffusion Models Are Statistically Optimal for Learning Low-Dimensional Multi-Modal Distributions](https://mlsanity.com/paper/2605.30153/) (2026)
- [Monotonic Risk Relationships under Distribution Shifts for Regularized Risk Minimization](https://mlsanity.com/paper/2210.11589/) (2022)
- [Provable Data Clustering via Innovation Search](https://mlsanity.com/paper/2108.06888/) (2021)
- [Greedier is Better: Selecting Multiple Neighbors per Iteration for Sparse Subspace Clustering](https://mlsanity.com/paper/2204.02572/) (2022)
- [ALPCAHUS: Subspace Clustering for Heteroscedastic Data](https://mlsanity.com/paper/2505.18918/) (2025)
- [Beyond Linear Subspace Clustering: A Comparative Study of Nonlinear Manifold Clustering Algorithms](https://mlsanity.com/paper/2103.10656/) (2021)
- [Neural Ordinary Differential Equation Model for Evolutionary Subspace Clustering and Its Applications](https://mlsanity.com/paper/2107.10484/) (2021)
- [Provable Clustering of a Union of Linear Manifolds Using Optimal Directions](https://mlsanity.com/paper/2201.02745/) (2022)
- [Revisiting data augmentation for subspace clustering](https://mlsanity.com/paper/2207.09728/) (2022)
- [Subspace Clustering in Wavelet Packets Domain](https://mlsanity.com/paper/2406.03819/) (2024)
- [Why the Metric Backbone Preserves Community Structure](https://mlsanity.com/paper/2406.03852/) (2024)
- [Label-independent hyperparameter-free self-supervised single-view deep subspace clustering](https://mlsanity.com/paper/2504.18179/) (2025)

## Abstract (arXiv)

The problem of clustering noisy and incompletely observed high-dimensional data points into a union of low-dimensional subspaces and a set of outliers is considered. The number of subspaces, their dimensions, and their orientations are assumed unknown. We propose a simple low-complexity subspace clustering algorithm, which applies spectral clustering to an adjacency matrix obtained by thresholding the correlations between data points. In other words, the adjacency matrix is constructed from the nearest neighbors of each data point in spherical distance. A statistical performance analysis shows that the algorithm exhibits robustness to additive noise and succeeds even when the subspaces intersect. Specifically, our results reveal an explicit tradeoff between the affinity of the subspaces and the tolerable noise level. We furthermore prove that the algorithm succeeds even when the data points are incompletely observed with the number of missing entries allowed to be (up to a log-factor) linear in the ambient dimension. We also propose a simple scheme that provably detects outliers, and we present numerical results on real and synthetic data.