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

Erdős-Rényi graphsnonbacktracking matricesrandom matricessparse matricesspectral radius

Mathematics Subject Classification ID

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

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.

Review text

The paper studies spectral radii of classes of random matrices of combinatorial interest, including the adjacency matrices of (inhomogeneous) Erdős-Rényi random graphs. It was already known from [\textit{Z. Füredi} and \textit{J. Komloś}, Combinatorica 1, 233--241 (1981; Zbl 0494.15010); \textit{V. H. Vu}, Combinatorica 27, No. 6, 721--736 (2007; Zbl 1164.05066)] that, for example, in the sparse Erdős-Rényi random graph \(G(n, d/n)\), the second and smallest adjacency eigenvalues converge to the edges of the support of the asymptotic eigenvalue distribution provided \(d/\log(n)^{4}\rightarrow \infty\). In this paper, these results are extended to a proof that the same statement holds under the weaker assumption that \(d/\log(n)\rightarrow\infty\). A companion paper of the authors shows that in the other regime \(d/\log(n)\rightarrow 0\) the behavior is different [Ann. Probab. 47, No. 3, 1653--1676 (2019; Zbl 1447.60017)]. The main new tool is a refined use of the non-backtracking matrix. It is important to emphasize that the results apply to a much more general class of random graphs, including block stochastic models and inhomogeneous Erdős-Rényi graphs.

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

• Concentration inequalities. A nonasymptotic theory of independence
• Expander graphs and their applications
• scientific article; zbMATH DE number 1189239 (Why is no real title available?)
• scientific article; zbMATH DE number 1495995 (Why is no real title available?)
• 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 dimension-free structure of nonhomogeneous random matrices
• The eigenvalues of random symmetric matrices
• The Rotation of Eigenvectors by a Perturbation. III

Cited in

(71)

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

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)