Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering
This work provides a finer statistical analysis for spectral clustering in mixture models, which is incremental but improves upon existing bounds for researchers in statistics and machine learning.
The authors tackled the problem of analyzing spectral clustering performance under mixture models by developing a leave-one-out singular subspace perturbation bound, which yields an explicit exponential error rate for sub-Gaussian mixtures and an optimal rate for isotropic Gaussians under weaker conditions.
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{ö}ffler et al. (2021).