Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering
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 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. Powered by this
leave-one-out perturbation theory, we provide a deterministic entrywise
analysis for the performance of the spectral clustering under mixture models.
Our analysis leads to an explicit exponential error rate for the 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).