Asymptotic Gaussian Fluctuations of Eigenvectors in Spectral Clustering

• URL: http://arxiv.org/abs/2402.12302v2
• Date: Mon, 27 May 2024 07:44:57 GMT
• Title: Asymptotic Gaussian Fluctuations of Eigenvectors in Spectral Clustering
• Authors: Hugo Lebeau, Florent Chatelain, Romain Couillet,
• Abstract summary: 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. This CLT-like result was the last missing piece to precisely predict the classification performance of spectral clustering.
• Score: 24.558241146742205
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Generalization for Least Squares Regression With Simple Spiked Covariances [3.9134031118910264]
  The generalization properties of even two-layer neural networks trained by gradient descent remain poorly understood. Recent work has made progress by describing the spectrum of the feature matrix at the hidden layer. Yet, the generalization error for linear models with spiked covariances has not been previously determined.
  arXiv  Detail & Related papers  (2024-10-17T19:46:51Z)
• High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularization [83.06112052443233]
  This paper studies kernel ridge regression in high dimensions under covariate shifts. By a bias-variance decomposition, we theoretically demonstrate that the re-weighting strategy allows for decreasing the variance. For bias, we analyze the regularization of the arbitrary or well-chosen scale, showing that the bias can behave very differently under different regularization scales.
  arXiv  Detail & Related papers  (2024-06-05T12:03:27Z)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• Analysis of singular subspaces under random perturbations [3.6626323701161665]
  We extend the Davis-Kahan-Wedin theorem in a fully generalized manner, applicable to any unitarily invariant matrix norm. We explore the practical implications of these findings, in the context of the Gaussian mixture model and the submatrix localization problem.
  arXiv  Detail & Related papers  (2024-03-14T08:30:25Z)
• Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction [55.57072563835959]
  spectral graph neural networks are characterized by filters. We propose an eigenvalue correction strategy that can free filters from the constraints of repeated eigenvalue inputs.
  arXiv  Detail & Related papers  (2024-01-28T08:12:00Z)
• Quantitative deterministic equivalent of sample covariance matrices with a general dependence structure [0.0]
  We prove quantitative bounds involving both the dimensions and the spectral parameter, in particular allowing it to get closer to the real positive semi-line. As applications, we obtain a new bound for the convergence in Kolmogorov distance of the empirical spectral distributions of these general models.
  arXiv  Detail & Related papers  (2022-11-23T15:50:31Z)
• When Random Tensors meet Random Matrices [50.568841545067144]
  This paper studies asymmetric order-$d$ spiked tensor models with Gaussian noise. We show that the analysis of the considered model boils down to the analysis of an equivalent spiked symmetric textitblock-wise random matrix.
  arXiv  Detail & Related papers  (2021-12-23T04:05:01Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• A simpler spectral approach for clustering in directed networks [1.52292571922932]
  We show that using the eigenvalue/eigenvector decomposition of the adjacency matrix is simpler than all common methods. We provide numerical evidence for the superiority of the Gaussian Mixture clustering over the widely used k-means algorithm.
  arXiv  Detail & Related papers  (2021-02-05T14:16:45Z)
• Statistical properties of structured random matrices [0.0]
  Spectral properties of Hermitian Toeplitz, Hankel, and Toeplitz-plus-Hankel random matrices with independent identically distributed entries are investigated. Our findings show that intermediate-type statistics is more ubiquitous and universal than was considered so far and open a new direction in random matrix theory.
  arXiv  Detail & Related papers  (2020-12-21T18:00:14Z)
• Sparse Quantized Spectral Clustering [85.77233010209368]
  We exploit tools from random matrix theory to make precise statements about how the eigenspectrum of a matrix changes under such nonlinear transformations. We show that very little change occurs in the informative eigenstructure even under drastic sparsification/quantization.
  arXiv  Detail & Related papers  (2020-10-03T15:58:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.