Extreme singular values of inhomogeneous sparse random rectangular matrices

Abstract

We develop a unified approach to bounding the largest and smallest singular values of an inhomogeneous random rectangular matrix, based on the non-backtracking operator and the Ihara-Bass formula for general random Hermitian matrices with a bipartite block structure. We obtain probabilistic upper (respectively, lower) bounds for the largest (respectively, smallest) singular values of a large rectangular random matrix $X$. These bounds are given in terms of the maximal and minimal ${\ell }_2$-norms of the rows and columns of the variance profile of $X$. The proofs involve finding probabilistic upper bounds on the spectral radius of an associated non-backtracking matrix $B$. The two-sided bounds can be applied to the centered adjacency matrix of sparse inhomogeneous Erdős-Rényi bipartite graphs for a wide range of sparsity, down to criticality. In particular, for Erdős-Rényi bipartite graphs $G(n,m,p)$ with $p=\omega (\log n)/n$, and $m/n\to y\in (0,1)$, our sharp bounds imply that there are no outliers outside the support of the Marčenko-Pastur law almost surely. This result extends the Bai-Yin theorem to sparse rectangular random matrices.

23 pages

References in corpus (16)

• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• The dimension-free structure of nonhomogeneous random matrices
• On the spectral norm of Gaussian random matrices
• Matrix Concentration Inequalities and Free Probability
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• ${\ell }_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
• Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation
• Almost sure convergence of the largest and smallest eigenvalues of high-dimensional sample correlation matrices
• Spectral Thresholds in the Bipartite Stochastic Block Model
• On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence
• A Graphon Approach to Limiting Spectral Distributions of Wigner-type Matrices
• Eigenvalues of the non-backtracking operator detached from the bulk
• A class of network models recoverable by spectral clustering
• Spectra of random regular hypergraphs
• On the second eigenvalue of random bipartite biregular graphs
• Universality and sharp matrix concentration inequalities