Spectral radii of sparse random matrices

DOI10.1214/19-AIHP1033MaRDI QIDQ2227480zbMATH OpenFDO

Authors Charles Bordenave, Antti Knowles, Florent Benaych-Georges

Publication date 15 February 2021

Published in Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.02945, https://projecteuclid.org/euclid.aihp/1593137322

zbMATH Keywords

sparse matricesspectral radiusrandom matricesnonbacktracking matricesErdős-Rényi graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Stochastic matrices (15B51)

Abstract: We establish bounds on the spectral radii for a large class of sparse random matrices, which includes the adjacency matrices of inhomogeneous ErdH{o}s-R'enyi graphs. Our error bounds are sharp for a large class of sparse random matrices. In particular, for the ErdH{o}s-R'enyi graph $G(n,d/n)$, our results imply that the smallest and second-largest eigenvalues of the adjacency matrix converge to the edges of the support of the asymptotic eigenvalue distribution provided that $dgglogn$. Together with the companion paper [3], where we analyse the extreme eigenvalues in the complementary regime $dlllogn$, this establishes a crossover in the behaviour of the extreme eigenvalues around $dsimlogn$. Our results also apply to non-Hermitian sparse random matrices, corresponding to adjacency matrices of directed graphs. The proof combines (i) a new inequality between the spectral radius of a matrix and the spectral radius of its nonbacktracking version together with (ii) a new application of the method of moments for nonbacktracking matrices.

Recommendations

• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Bulk eigenvalue fluctuations of sparse random matrices
• Sparse random graphs: eigenvalues and eigenvectors
• Sparse random matrices have simple spectrum
• Sparse regular random graphs: spectral density and eigenvectors

Cites work

• scientific article; zbMATH DE number 1189239 (Why is no real title available?)
• scientific article; zbMATH DE number 1495995 (Why is no real title available?)
• Concentration inequalities. A nonasymptotic theory of independence
• Expander graphs and their applications
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Local semicircle law for Wigner matrices
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• On the limit of the largest eigenvalue of the large dimensional sample covariance matrix
• On the second eigenvalue and random walks in random \(d\)-regular graphs
• On the spectra of general random graphs
• Random matrices, nonbacktracking walks, and orthogonal polynomials
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Sparse random matrices; Spectral edge and statistics of rooted trees
• Spectral norm of random matrices
• Spectral redemption in clustering sparse networks
• Spectral techniques applied to sparse random graphs
• The Rotation of Eigenvectors by a Perturbation. III
• The dimension-free structure of nonhomogeneous random matrices
• The eigenvalues of random symmetric matrices

Cited in

(54)

• Fluctuations of extreme eigenvalues of sparse Erdős-Rényi graphs
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs
• The skew spectral radius and skew Randić spectral radius of general random oriented graphs
• Scalable estimation of epidemic thresholds via node sampling
• Random geometric graph: some recent developments and perspectives
• Extremal eigenvalues of critical Erdős-Rényi graphs
• Spectral large deviations of sparse random matrices
• Asymptotic Absence of Poles of Ihara Zeta Function of Large Erdős–Rényi Random Graphs
• Equilibria of large random Lotka-Volterra systems with vanishing species: a mathematical approach
• Concentration of the spectral norm of Erdős-Rényi random graphs
• Sparse random tensors: concentration, regularization and applications
• On the spectral radius of a random matrix: an upper bound without fourth moment
• Poisson statistics and localization at the spectral edge of sparse Erdős-Rényi graphs
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• scientific article; zbMATH DE number 5994989 (Why is no real title available?)
• Outliers in spectrum of sparse Wigner matrices
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Banach space actions and \(L^2\)-spectral gap
• Spectral edge in sparse random graphs: upper and lower tail large deviations
• Sparse matrices: convergence of the characteristic polynomial seen from infinity
• Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
• Sparse random matrices have simple spectrum
• Spectral gap of sparse bistochastic matrices with exchangeable rows
• Tail bounds for gaps between eigenvalues of sparse random matrices
• Delocalization transition for critical Erdős-Rényi graphs
• Lack of hyperbolicity in asymptotic Erdős-Renyi sparse random graphs
• Universality of approximate message passing algorithms and tensor networks
• Random matrices: overcrowding estimates for the spectrum
• Algebraic and combinatorial expansion in random simplicial complexes
• Spectra of sparse random matrices
• Rigidity of eigenvalues for \(\beta\) ensemble in multi-cut regime
• Estimating the number of communities by spectral methods
• The Second Eigenvalue of Random Walks On Symmetric Random Intersection Graphs
• Detection thresholds in very sparse matrix completion
• Patterned sparse random matrices: A moment approach
• Spectra of large diluted but bushy random graphs
• Eigenvector statistics of sparse random matrices
• Sparse random graphs: eigenvalues and eigenvectors
• The spectral norm of random lifts of matrices
• Eigenvectors of a matrix under random perturbation
• Spectra of adjacency and Laplacian matrices of inhomogeneous Erdős-Rényi random graphs
• Sparse random hypergraphs: non-backtracking spectra and community detection
• Sparse random matrices: the eigenvalue spectrum revisited
• The completely delocalized region of the Erdős-Rényi graph
• Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
• Sparse random matrices; Spectral edge and statistics of rooted trees
• The spectral gap of sparse random digraphs
• Spectrum of Markov generators on sparse random graphs
• Non-backtracking spectra of weighted inhomogeneous random graphs
• Eigenvalues of the non-backtracking operator detached from the bulk
• Comment: Ridge Regression and Regularization of Large Matrices
• Upper tail of the spectral radius of sparse Erdös-Rényi graphs
• On the spectrum of dense random geometric graphs

This page was built for publication: Spectral radii of sparse random matrices

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