# Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 66 references that are in the map.
- First posted on arXiv 11 Jun 2022.

## Builds on (most cited first, 21 of 21)

- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit](https://mlsanity.com/paper/1507.01238/) (2015)
- [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013)
- [Nonconvex phase synchronization](https://mlsanity.com/paper/1601.06114/) (2016)
- [From Symmetry to Geometry: Tractable Nonconvex Problems](https://mlsanity.com/paper/2007.06753/) (2020)
- [Robust subspace clustering](https://mlsanity.com/paper/1301.2603/) (2013)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [Noisy Sparse Subspace Clustering](https://mlsanity.com/paper/1309.1233/) (2013)
- [Stochastic Sparse Subspace Clustering](https://mlsanity.com/paper/2005.01449/) (2020)
- [Robust Subspace Clustering via Thresholding](https://mlsanity.com/paper/1307.4891/) (2013)
- [Large-Scale Subspace Clustering via k-Factorization](https://mlsanity.com/paper/2012.04345/) (2020)
- [Alternating Minimization Converges Super-Linearly for Mixed Linear Regression](https://mlsanity.com/paper/2004.10914/) (2020)
- [Greedy Feature Selection for Subspace Clustering](https://mlsanity.com/paper/1303.4778/) (2013)
- [Sketched Subspace Clustering](https://mlsanity.com/paper/1707.07196/) (2017)
- [Greedy Subspace Clustering](https://mlsanity.com/paper/1410.8864/) (2014)
- [Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method](https://mlsanity.com/paper/2106.05644/) (2021)
- [Subspace Clustering using Ensembles of K-Subspaces](https://mlsanity.com/paper/1709.04744/) (2017)
- [Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method](https://mlsanity.com/paper/2012.00470/) (2020)
- [Noisy subspace clustering via matching pursuits](https://mlsanity.com/paper/1612.03450/) (2016)
- [Non-Convex Exact Community Recovery in Stochastic Block Model](https://mlsanity.com/paper/2006.15843/) (2020)
- [Theory of Spectral Method for Union of Subspaces-Based Random Geometry Graph](https://mlsanity.com/paper/1907.10906/) (2019)

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

- [Breaking the Curse of Dimensionality: Diffusion Models Efficiently Learn Low-Dimensional Distributions](https://mlsanity.com/paper/2409.02426/) (2024)
- [Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifold](https://mlsanity.com/paper/2209.09211/) (2022)
- [Understanding Representation Dynamics of Diffusion Models via Low-Dimensional Modeling](https://mlsanity.com/paper/2502.05743/) (2025)
- [Unsupervised Manifold Linearizing and Clustering](https://mlsanity.com/paper/2301.01805/) (2023)
- [Attention-Only Transformers via Unrolled Subspace Denoising](https://mlsanity.com/paper/2506.03790/) (2025)
- [High-dimensional Clustering onto Hamiltonian Cycle](https://mlsanity.com/paper/2304.14531/) (2023)
- [ALPCAHUS: Subspace Clustering for Heteroscedastic Data](https://mlsanity.com/paper/2505.18918/) (2025)
- [Affine Subspace Models and Clustering for Patch-Based Image Denoising](https://mlsanity.com/paper/2512.07259/) (2025)
- [Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy](https://mlsanity.com/paper/2608.14215/) (2026)

## Abstract (arXiv)

The K-subspaces (KSS) method is a generalization of the K-means method for subspace clustering. In this work, we present local convergence analysis and a recovery guarantee for KSS, assuming data are generated by the semi-random union of subspaces model, where N points are randomly sampled from K ≥ 2 overlapping subspaces. We show that if the initial assignment of the KSS method lies within a neighborhood of a true clustering, it converges at a superlinear rate and finds the correct clustering within Theta(loglog N) iterations with high probability. Moreover, we propose a thresholding inner-product based spectral method for initialization and prove that it produces a point in this neighborhood. We also present numerical results of the studied method to support our theoretical developments.