Spectral radii of sparse random matrices

DOI10.1214/19-AIHP1033zbMATH Open1459.15036arXiv1704.02945MaRDI QIDQ2227480FDOQ2227480

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)

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.

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

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

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)

Cites Work

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

Cited In (54)

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

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)