# Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 52 references that are in the map.
- First posted on arXiv 30 May 2022.

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

- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel](https://mlsanity.com/paper/1309.4111/) (2013)
- [Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics](https://mlsanity.com/paper/1605.00353/) (2016)
- [Optimality of Spectral Clustering in the Gaussian Mixture Model](https://mlsanity.com/paper/1911.00538/) (2019)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit](https://mlsanity.com/paper/2012.09996/) (2020)
- [Analysis of spectral clustering algorithms for community detection: the general bipartite setting](https://mlsanity.com/paper/1803.04547/) (2018)
- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [The geometry of kernelized spectral clustering](https://mlsanity.com/paper/1404.7552/) (2014)
- [Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence](https://mlsanity.com/paper/2105.13346/) (2021)
- [A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers](https://mlsanity.com/paper/1912.07546/) (2019)
- [Efficient Clustering for Stretched Mixtures: Landscape and Optimality](https://mlsanity.com/paper/2003.09960/) (2020)
- [Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates](https://mlsanity.com/paper/2002.07624/) (2020)

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

- [Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Bound](https://mlsanity.com/paper/2212.08642/) (2022)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Efficient and Accurate Learning of Mixtures of Plackett-Luce Models](https://mlsanity.com/paper/2302.05343/) (2023)
- [Heteroskedastic Tensor Clustering](https://mlsanity.com/paper/2311.02306/) (2023)
- [Optimal Clustering of Discrete Mixtures: Binomial, Poisson, Block Models, and Multi-layer Networks](https://mlsanity.com/paper/2311.15598/) (2023)
- [Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learning](https://mlsanity.com/paper/2304.09154/) (2023)
- [Consistency of Lloyd's Algorithm Under Perturbations](https://mlsanity.com/paper/2309.00578/) (2023)
- [A Novel and Optimal Spectral Method for Permutation Synchronization](https://mlsanity.com/paper/2303.12051/) (2023)
- [Factor Adjusted Spectral Clustering for Mixture Models](https://mlsanity.com/paper/2408.12564/) (2024)
- [Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms](https://mlsanity.com/paper/2501.11139/) (2025)
- [High-dimensional Clustering and Signal Recovery under Block Signals](https://mlsanity.com/paper/2504.08332/) (2025)
- [Goodness-of-Fit Tests for Latent Class Models with Ordinal Categorical Data](https://mlsanity.com/paper/2602.21572/) (2026)
- [Individual-heterogeneous sub-Gaussian Mixture Models](https://mlsanity.com/paper/2604.05337/) (2026)
- [Mixed Membership sub-Gaussian Models](https://mlsanity.com/paper/2604.22633/) (2026)
- [Geometric bias in eigenspace perturbation under random heterogeneous noise](https://mlsanity.com/paper/2606.11263/) (2026)

## Abstract (arXiv)

The singular subspaces perturbation theory is of fundamental importance in probability and statistics. It has various applications across different fields. We consider two arbitrary matrices where one is a leave-one-column-out submatrix of the other one and establish a novel perturbation upper bound for the distance between the two corresponding singular subspaces. It is well-suited for mixture models and results in a sharper and finer statistical analysis than classical perturbation bounds such as Wedin's Theorem. Empowered by this leave-one-out perturbation theory, we provide a deterministic entrywise analysis for the performance of spectral clustering under mixture models. Our analysis leads to an explicit exponential error rate for spectral clustering of sub-Gaussian mixture models. For the mixture of isotropic Gaussians, the rate is optimal under a weaker signal-to-noise condition than that of L"offler et al. (2021).