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

Source: [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](<https://www.sota2.com/research/paper/68fa5b4a1e209131ce9c6e29>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T16:57:33.111Z

Authors: Anderson Y. Zhang, Harrison H. Zhou

Published: 2022-05-30T05:07:09.000Z

## Abstract

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{\\"o}ffler et al. (2021).

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Classification on Seeds (Misclassification Count)](<https://www.sota2.com/research/sota/classification-on-seeds-misclassification-count.md>): Classification; SEEDS; Misclassification Count: 16.

- [Classification on Iris (Misclassification Count)](<https://www.sota2.com/research/sota/classification-on-iris-misclassification-count.md>): Classification; Iris; Misclassification Count: 16.

- [Classification on Wine (Misclassification Count)](<https://www.sota2.com/research/sota/classification-on-wine-misclassification-count.md>): Classification; Wine; Misclassification Count: 7.

- [Image Segment Classification on segment](<https://www.sota2.com/research/sota/image-segment-classification-on-segment.md>): Image Segment Classification; segment; Misclassification Count: 770.

- [Satellite Image Classification on satimage (train)](<https://www.sota2.com/research/sota/satellite-image-classification-on-satimage-train.md>): Satellite Image Classification; satimage (train); Misclassification Count: 1468.

- [Classification on DNA](<https://www.sota2.com/research/sota/classification-on-dna.md>): Classification; DNA; Misclassification Count: 580.

- [Handwritten Digit Classification on USPS (train)](<https://www.sota2.com/research/sota/handwritten-digit-classification-on-usps-train.md>): Handwritten digit classification; usps (train); Error Count: 2360.

- [Handwritten Digit Classification on pendigits (train)](<https://www.sota2.com/research/sota/handwritten-digit-classification-on-pendigits-train.md>): Handwritten digit classification; pendigits (train); Misclassification Rate: 0.32599412863624233.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2205.14855>)

[PDF](<https://arxiv.org/pdf/2205.14855.pdf>)