mlsanityData to 14 Oct 2026

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

arXiv 2206.05553 ↗First posted 11 Jun 2022math.OC stat.MLcited by 9

Not on the map. Why?

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.

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

21 of 66 references.

References · 21

  1. 2013Consistency of spectral clustering in stochastic block modelscited by 129
  2. 2015Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuitcited by 50
  3. 2013Understanding Alternating Minimization for Matrix Completioncited by 32
  4. 2016Nonconvex phase synchronizationcited by 30
  5. 2020From Symmetry to Geometry: Tractable Nonconvex Problemscited by 29
  6. 2013Robust subspace clusteringcited by 24
  7. 2019Iterative Algorithm for Discrete Structure Recoverycited by 21
  8. 2013Noisy Sparse Subspace Clusteringcited by 18
  9. 2020Stochastic Sparse Subspace Clusteringcited by 17
  10. 2013Robust Subspace Clustering via Thresholdingcited by 16
  11. 2020Large-Scale Subspace Clustering via k-Factorizationcited by 14
  12. 2020Alternating Minimization Converges Super-Linearly for Mixed Linear Regressioncited by 12
9 more
  1. 2013Greedy Feature Selection for Subspace Clusteringcited by 11
  2. 2017Sketched Subspace Clusteringcited by 11
  3. 2014Greedy Subspace Clusteringcited by 10
  4. 2021Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Methodcited by 10
  5. 2017Subspace Clustering using Ensembles of K-Subspacescited by 7
  6. 2020Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Methodcited by 7
  7. 2016Noisy subspace clustering via matching pursuitscited by 5
  8. 2020Non-Convex Exact Community Recovery in Stochastic Block Modelcited by 5
  9. 2019Theory of Spectral Method for Union of Subspaces-Based Random Geometry Graphcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 1; 2025: 4; 2026: 1.

9 papers.

  1. 2024Breaking the Curse of Dimensionality: Diffusion Models Efficiently Learn Low-Dimensional Distributionscited by 53
  2. 2022Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifoldcited by 50
  3. 2025Understanding Representation Dynamics of Diffusion Models via Low-Dimensional Modelingcited by 18
  4. 2023Unsupervised Manifold Linearizing and Clusteringcited by 12
  5. 2025Attention-Only Transformers via Unrolled Subspace Denoisingcited by 5
  6. 2023High-dimensional Clustering onto Hamiltonian Cyclecited by 2
  7. 2025ALPCAHUS: Subspace Clustering for Heteroscedastic Datacited by 1
  8. 2025Affine Subspace Models and Clustering for Patch-Based Image Denoisingcited by 0
  9. 2026Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesycited by 0