Inverse Littlewood-Offord theorems and the condition number of random discrete matrices

By Terence Tao, Van H. Vu. 2005

225 citations recorded by the source corpus.

Consider a random sum r)\V\ + • • • + r]nvn, where 771, . . . , rin are independently and identically distributed (i.i.d.) random signs and vi, . . . , vn are integers. The Littlewood-Offord problem asks to maximize concentration probabilities such as P(r?i^iH In this paper we develop an inverse Littlewood-Offord theory (somewhat in the spirit of Freiman's inverse theory in additive combinatorics), which starts with the hypothesis that a concentration probability is large, and concludes that almost all of the v\ , . . . , vn are efficiently contained in a generalized arithmetic progression. As an application we give a new bound on the magnitude of the

Subfields: Discrete Mathematics and Combinatorics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/7aaf1da7bcd026dfeab04e3fd54b5cf0c6eadcbe

How researchers see this paper

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

In Discrete Mathematics and Combinatorics

In Statistics and Probability

Citations in the corpus

On the singularity of adjacency matrices for random regular digraphs (2014, result): “Polynomial lower bounds on the least singular value of general iid matrices were first obtained by Rudelson in [31], and were subsequently improved by Tao and Vu [41] and Rudelson and Vershynin [33].”
Adjacency matrices of random digraphs: singularity and anti-concentration (2015, methodology): “For more information and further references, we refer the reader to [32], [33, Section 3], and [29, Section 4].”
RANDOM MATRICES: THE CIRCULAR LAW (2007, methodology): “This was done building upon the M = 0 case discussed in [27].”
Singularity of random Bernoulli matrices (2018, methodology): “Note that this approach can be related to the inverse Littlewood–Offord theory started in [18], although here we are only interested in estimating from above the “size” of the set of potential normal vectors with large thresholds, rather than giving an explicit description of this set (in that respe”
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].”
Random matrices: Universality of local spectral statistics of non-Hermitian matrices (2012, background): “The proof of this bound relies heavily on the so-called inverse LittlewoodOfford theory introduced by the authors in [51], which was motivated by Additive Combinatorics (see [50, Chapter 7]), a seemingly unrelated area.”
Lower bounds for the smallest singular value of structured random matrices (2016, methodology): “Around the same time, in [37] Tao and Vu used methods from additive”
Random Matrices: the Distribution of the Smallest Singular Values (2009, unknown): “Thus we have the following extension of Theorem 1.3.”
Around the circular law (2011, background): “Following [102], it could probably be improved by using finer results on the LittlewoodOfford problem [147].”
Concentration inequalities for random tensors (2019, unknown): “For d = 1, this problem has been extensively studied in random matrix theory [16, 31, 23, 32, 25, 3, 26, 34, 27, 13, 10, 35, 36].”
Approximating the Spectral Sums of Large-scale Matrices using Chebyshev Approximations (2016, background): “, random matrices [42, 41] and diagonal-dominant matrices [20, 33].”