Tail bounds for gaps between eigenvalues of sparse random matrices
The authors study the eigenvalue gaps of sparse random matrices. The theory of sparse random matrices is of interest in its own right, but it also has innumerable applications in computer science and statistics. In contexts where sparse random matrices have similar spectral guarantees as their dense counterparts, they offer significant advantages as they require less space to store, allow quicker multiplication, and fewer random bits is necessary to generate them. The main contribution of the paper is to go beyond verifying the fact that such matrices have simple spectrum, and prove a tail bound for the minimal eigenvalue gap of these sparse random matrices. So, the first eigenvalue repulsion bound for sparse random matrices is established. As a consequence, it is proved that these matrices have simple spectrum, improving the range of sparsity and error probability from the previous works. It is also proved that for sparse Erdős-Rényi graphs, weak and strong nodal domains are the same.
- A sparse Johnson-Lindenstrauss transform
- An eigendecomposition approach to weighted graph matching problems
- Bulk universality for generalized Wigner matrices with few moments
- Bulk universality for Wigner matrices
- Bulk universality of sparse random matrices
- Change of variables as a method to study general β-models: Bulk universality
- Comparison theorem for some extremal eigenvalue statistics
- Eigenfunctions and nodal sets
- Eigenvector statistics of sparse random matrices
- Eigenvectors of random graphs: nodal domains
- Eigenvectors of random matrices: A survey
- Entrywise bounds for eigenvectors of random graphs
- Exploiting multiple levels of parallelism in sparse matrix-matrix multiplication
- Extreme gaps between eigenvalues of random matrices
- Gap universality of generalized Wigner and \(\beta\)-ensembles
- GOE statistics for Lévy matrices
- scientific article; zbMATH DE number 1313392 (Why is no real title available?)
- Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
- Invertibility of random matrices: norm of the inverse
- Invertibility of sparse non-Hermitian matrices
- Invertibility of symmetric random matrices
- Local law and Tracy-Widom limit for sparse random matrices
- Local spectral statistics of the addition of random matrices
- Nodal domains and spectral minimal partitions
- On the Number of Nodal Domains for Eigenfunctions of Elliptic Differential Operators
- On the second eigenfunctions of the Laplacian in \({\mathbb{R}}^ 2\)
- Random covariance matrices: universality of local statistics of eigenvalues
- Random matrices have simple spectrum
- Random matrices: tail bounds for gaps between eigenvalues
- Random matrices: the four-moment theorem for Wigner ensembles
- Random matrices: universality of local eigenvalue statistics
- Random matrices: Universality of local eigenvalue statistics up to the edge
- Rigidity of eigenvalues of generalized Wigner matrices
- Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
- Size of nodal domains of the eigenvectors of a G(n,p) graph
- Small ball probability, inverse theorems, and applications
- Small gaps of circular \(\beta \)-ensemble
- Small gaps of GOE
- Smallest singular value of random matrices and geometry of random polytopes
- Smallest singular value of sparse random matrices
- Sparse random matrices have simple spectrum
- Sparse signal recovery using a new class of random matrices
- Spectral statistics of Erdős-Rényi graphs II: eigenvalue spacing and the extreme eigenvalues
- Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
- The asymptotic distribution of a single eigenvalue gap of a Wigner matrix
- The Littlewood-Offord problem and invertibility of random matrices
- Transport maps for \(\beta\)-matrix models and universality
- Universality and the circular law for sparse random matrices
- Universality in several-matrix models via approximate transport maps
- Universality of covariance matrices
- Universality of random matrices and local relaxation flow
- Universality of random matrices with correlated entries
- Universality of the least singular value for sparse random matrices
- Vanishingly Sparse Matrices and Expander Graphs, With Application to Compressed Sensing
- Wegner Estimate and Level Repulsion for Wigner Random Matrices
- Noise sensitivity for the top eigenvector of a sparse random matrix
- Random matrices: tail bounds for gaps between eigenvalues
- On the smallest singular value of symmetric random matrices
- Smallest gaps between eigenvalues of real Gaussian matrices
- Solving sparse linear systems faster than matrix multiplication
- Phase transition for the bottom singular vector of rectangular random matrices
- Quantitative gap universality for Wigner matrices
This page was built for publication: Tail bounds for gaps between eigenvalues of sparse random matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2076604)
