Noise sensitivity for the top eigenvector of a sparse random matrix

DOI10.1214/22-EJP770zbMATH Open1489.15048arXiv2106.09570OpenAlexW3171053211MaRDI QIDQ2136103FDOQ2136103

Charles Bordenave, Jaehun Lee

Publication date: 10 May 2022

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Abstract: We investigate the noise sensitivity of the top eigenvector of a sparse random symmetric matrix. Let $v$ be the top eigenvector of an $NimesN$ sparse random symmetric matrix with an average of $d$ non-zero centered entries per row. We resample $k$ randomly chosen entries of the matrix and obtain another realization of the random matrix with top eigenvector $v^{[k]}$. Building on recent results on sparse random matrices and a noise sensitivity analysis previously developed for Wigner matrices, we prove that, if $dgeq{N}^{2/9}$, with high probability, when $kll{N}^{5/3}$, the vectors $v$ and $v^{[k]}$ are almost collinear and, on the contrary, when $kgg{N}^{5/3}$, the vectors $v$ and $v^{[k]}$ are almost orthogonal. A similar result holds for the eigenvector associated to the second largest eigenvalue of the adjacency matrix of an ErdH{o}s-R'enyi random graph with average degree $dgeq{N}^{2/9}$.

Full work available at URL: https://arxiv.org/abs/2106.09570

Recommendations

• Noise sensitivity of the top eigenvector of a Wigner matrix
• Asymptotic Eigenvalue Density of Noise Covariance Matrices
• High dimensional normality of noisy eigenvectors
• Eigenvector statistics of sparse random matrices
• Matrix denoising with partial noise statistics: optimal singular value shrinkage of spiked F-matrices
• Sparse random matrices: the eigenvalue spectrum revisited
• On the spectrum of noisy blown-up matrices
• The eigenvalues of very sparse random symmetric matrices
• On the empirical distribution of eigenvalues of large dimensional information-plus-noise-type matrices
• Bulk eigenvalue fluctuations of sparse random matrices

zbMATH Keywords

noise sensitivitysparse random matrix

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Cites Work

• Noise sensitivity of Boolean functions and applications to percolation
• The Largest Eigenvalue of Sparse Random Graphs
• The isotropic semicircle law and deformation of Wigner matrices
• Spectral statistics of Erdős-Rényi graphs II: eigenvalue spacing and the extreme eigenvalues
• Title not available (Why is that?)
• Noise Sensitivity of Boolean Functions and Percolation
• No-gaps delocalization for general random matrices
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• Universality of sine-kernel for Wigner matrices with a small Gaussian perturbation
• Stein's method for concentration inequalities
• Superconcentration and Related Topics
• Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
• Local law and Tracy-Widom limit for sparse random matrices
• A Dynamical Approach to Random Matrix Theory
• Noise sensitivity of the top eigenvector of a Wigner matrix
• Eigenvector statistics of sparse random matrices
• Local law and complete eigenvector delocalization for supercritical Erdős-Rényi graphs
• Sparse random matrices have simple spectrum
• Fluctuations of extreme eigenvalues of sparse Erdős-Rényi graphs
• Transition from Tracy-Widom to Gaussian fluctuations of extremal eigenvalues of sparse Erdős-Rényi graphs
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Size of nodal domains of the eigenvectors of a graph
• Tail bounds for gaps between eigenvalues of sparse random matrices

Cited In (3)

• Limiting Eigenvectors of Outliers for Spiked Information-Plus-Noise Type Matrices
• Noise sensitivity of the top eigenvector of a Wigner matrix
• Higher order fluctuations of extremal eigenvalues of sparse random matrices

This page was built for publication: Noise sensitivity for the top eigenvector of a sparse random matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136103)