Universality and the circular law for sparse random matrices.

By Philip Matchett Wood. 2010

63 citations recorded by the source corpus.

The universality phenomenon asserts that the distribution of the eigenvalues of random matrix with i.i.d. zero mean, unit variance entries does not depend on the underlying structure of the random entries. For example, a plot of the eigenvalues of a random sign matrix, where each entry is +1 or -1 with equal probability, looks the same as an analogous plot of the eigenvalues of a random matrix where each entry is complex Gaussian with zero mean and unit variance. In the current paper, we prove a universality result for sparse random n by n matrices where each entry is nonzero with probability $1/n^{1-\alpha}$ where $0<\alpha\le1$ is any constant. One consequence of the sparse universality principle is that the circular law holds for sparse random matrices so long as the entries have zero mean and unit variance, which is the most general result for sparse random matrices to date.

Subfields: Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/9921e59b20aad361833d19f6cc072f345e714ebd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Around the circular law (2011, background): “This extension contains for instance sparse models in which the law has an atom at 0 with mass pn → 1 at a certain speed, see [66, 145, 155].”
OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings (2012, unknown): “[28, 29, 50]).”
Spectrum of Markov Generators on Sparse Random Graphs (2012, background): “10) improves over previous works [23, 45] where the variance is assumed to satisfy n(1) " 2 ! 1 for some " > 0.”
Invertibility of Sparse non-Hermitian matrices (2015, background): “ singular values, especially the one on the smallest singular value, play a key role in obtaining the limiting spectral distribution of various non-Hermitian random matrix ensembles. For example, see [3, 6, 10, 11, 18, 24, 30, 35]. Likewise, the bounds on the smallest singular value obtained here pl”
Sparse Matrix Factorization (2013, background): “In a recent work, [16] extends the circular law on the distribution of the eigenvalues to that of sparse random matrices but it does not establish lower bounds on the smallest eigenvalue.”
The stability–complexity relationship at age 40: a random matrix perspective (2015, background): “However, for the circular law to hold (Wood 2012), we need that SC !”
A Proof of the Block Model Threshold Conjecture (2013, background): “For example, semi-circle laws and local statistics are now known whenever a and b are growing at least logarithmically fast in n [29] (following earlier work that required polynomially fast growth [11,28]), and also for matrix ensembles with more general i.i.d. entries.”