2025/08/02 by Ioana Dumitriu, Dumitriu, Ioana, Hai‐Xiao Wang +5
Mathematics · #Random Matrices and Applications #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2508.01456
Consider the random bipartite Erdős-Rényi graph \mathbbG(n, m, p), where each edge with one vertex in V1=[n] and the other vertex in V2 =[m] is connected with probability p, and n=\lfloor γm\rfloor for a constant aspect ratio γ≥ 1. It is well known that the empirical spectral measure of its centered and normalized adjacency matrix converges to the Marčenko-Pastur (MP) distribution. However, largest and smallest singular values may not converge to the right and left edges, respectively, especially when p = o(1). Notably, it was proved by Dumitriu and Zhu (2024) that there are almost surely no singular value outside the compact support of the MP law when np = ω(log(n)). In this paper, we consider the critical sparsity regime where p = blog(n)/√(mn) for some constant b>0. We quantitatively characterize the emergence of outlier singular values as follows. For explicit b* and b* as functions of γ, we prove that when b > b*, there is no outlier outside the bulk; when b*< b < b*, outliers are present only outside the right edge of the MP law; and when b < b*, outliers are present on both sides, all with high probability. Moreover, the locations of those outliers are precisely characterized by a function depending on the largest and smallest degree vertices of the random graph. We estimate the number of outliers as well. Our results follow the path forged by Alt, Ducatez and Knowles (2021), and can be extended to sparse random rectangular matrices with bounded entries.