From the Littlewood-Offord problem to the Circular Law: universality of the spectral distribution of random matrices

By Terence Tao, Van H. Vu. 2008

137 citations recorded by the source corpus.

The famous \emph{circular law} asserts that if $M_n$ is an $n \times n$ matrix with iid complex entries of mean zero and unit variance, then the empirical spectral distribution (ESD) of the normalized matrix $\frac{1}{\sqrt{n}} M_n$ converges almost surely to the uniform distribution on the unit disk $\{z \in \C: |z| \leq 1 \}$. After a long sequence of partial results that verified this law under additional assumptions on the distribution of the entries, the full circular law was recently established in \cite{TVcir2}. In this survey we describe some of the key ingredients used in the establishment of the circular law, in particular recent advances in understanding the Littlewood-Offord problem and its inverse.

Subfields: Applied Mathematics, Discrete Mathematics and Combinatorics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/918d3f045df2d3412f87f088d5eed13158912f78

How researchers see this paper

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

In Applied Mathematics

In Discrete Mathematics and Combinatorics

In Statistics and Probability

Citations in the corpus

Intersection bounds: estimation and inference (2009, methodology): “…sequence of Gaussian processes, in contrast to a vast knowledge on the concentration properties of such processes (see however Rudelson and Vershynin (2007), Rudelson and Vershynin (2008) and Tao and Vu (2009) for a discussion of anti-concentration inequalities for some “simpler” related problems).”
Random matrices: Universality of local spectral statistics of non-Hermitian matrices (2012, methodology): “This is the route taken, for instance, to establish the circular law for iid matrices; see [53, 5] for further discussion.”
Non-asymptotic theory of random matrices: extreme singular values (2010, methodology): “New results on Lévy concentration function Problems of invertibility of random matrices motivated a recent revisiting of the Littlewood-Offord problem by Tao and Vu [83, 84, 86, 88], the authors [65, 67], Friedland and Sodin [27].”
No-gaps delocalization for general random matrices (2015, background): “Recent successes in these problems were based on understanding the interaction of probability with arithmetic structure, which was quantified via generalized arithmetic progressions in [32, 31] and approximate least common denominators (LCD) in [23, 25, 38]; see [33, 26] for background and reference”
Random matrices: tail bounds for gaps between eigenvalues (2015, background): “[22,30]) and by Rudelson and Vershynin (see e.”
Introduction to the non-asymptotic analysis of random matrices (2010, background): “The surveys [76, 69] discuss this problem at length, and they offer a glimpse of connections to other problems of random matrix theory and additive combinatorics.”
The Elliptic Law (2012, background): “It was shown implicitly by Tao and Vu in [42, 45, 48] that these are essentially the only examples that have high concentration probability.”
Optimal Inverse Littlewood-Offord theorems (2010, background): “12 is at the heart of establishing the Circular Law conjecture in random matrix theory (see [21, 17]).”
Universality and the circular law for sparse random matrices. (2010, background): “10, is the current best result, requiring only zero mean and unit variance (see also [33]).”
Outlier Eigenvalues for Deformed I.I.D. Random Matrices (2014, methodology): “For more references, we refer to the surveys [52, 17].”
Small Ball Probability, Inverse Theorems, and Applications (2012, background): “For applications in Random Matrix Theory (such as the establishment of the Circular Law) and many related results, we refer to [59, 65, 58, 18, 40, 2, 47] and the references therein.”
Statistics of Group Delays in Multimode Fiber With Strong Mode Coupling (2011, background): “The Wigner semicircle law is universally valid for many different types of large random matrices [45], [46].”
Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices (2019, methodology): “It could be interesting to see if the bound of Theorem 4 can be extended to this case (for instance in the case of centered, variance 1 independent coordinates with bounded density, as in Section 3.3), by leveraging the techniques from [RV08, RV09, TV09b, TV09a].”
Small Ball Probabilities for Linear Images of High-Dimensional Distributions (2014, unknown): “44 92 v1 [ m at h. PR ] 1 8 Fe b 20 14 0.9 r(A), where r(A) denotes the stable rank of A.”
Around the circular law (2011, unknown): “See also their synthetic paper [146].”