Asymptotic Gaussian Fluctuations of Eigenvectors in Spectral Clustering
This provides a theoretical foundation for predicting spectral clustering performance, addressing a key gap in machine learning theory.
The paper tackled the problem of characterizing fluctuations in spectral clustering eigenvectors, showing that in a general spike random matrix model, the entries of eigenvectors exhibit Gaussian fluctuations in the large-dimensional regime, enabling precise prediction of classification performance.
The performance of spectral clustering relies on the fluctuations of the entries of the eigenvectors of a similarity matrix, which has been left uncharacterized until now. In this letter, it is shown that the signal $+$ noise structure of a general spike random matrix model is transferred to the eigenvectors of the corresponding Gram kernel matrix and the fluctuations of their entries are Gaussian in the large-dimensional regime. This CLT-like result was the last missing piece to precisely predict the classification performance of spectral clustering. The proposed proof is very general and relies solely on the rotational invariance of the noise. Numerical experiments on synthetic and real data illustrate the universality of this phenomenon.