The Littlewood-Offord problem and invertibility of random matrices

By Mark Rudelson, Roman Vershynin. 2007

459 citations recorded by the source corpus.

Abstract We prove two basic conjectures on the distribution of the smallest singular value of random n × n matrices with independent entries. Under minimal moment assumptions, we show that the smallest singular value is of order n − 1 / 2 , which is optimal for Gaussian matrices. Moreover, we give a optimal estimate on the tail probability. This comes as a consequence of a new and essentially sharp estimate in the Littlewood–Offord problem: for i.i.d. random variables X k and real numbers a k , determine the probability p that the sum ∑ k a k X k lies near some number v . For arbitrary coefficients a k of the same order of magnitude, we show that they essentially lie in an arithmetic progression of length 1 / p .

Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/2ec824d7f47b95d241897c08d4106b1f9937460e

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 Mathematical Physics

In Statistics and Probability

Citations in the corpus

Non-asymptotic theory of random matrices: extreme singular values (2010, background): “4 (Distance between random vectors and hyperplanes [65]).”
Tight Sample Complexity of Large-Margin Learning (2010, background): “In the following Theorem we generalize results of Rudelson and Vershynin to encompass also non-identically distributed coordinates.”
The least singular value of a random square matrix is O(n−1/2) (2008, methodology): “The same result but with the reverse estimate, P (s n (A) Kn − 1 / 2 ) (cid:2) δ , was proved in [2].”
Random matrices: Universality of local spectral statistics of non-Hermitian matrices (2012, background): “Interestingly, this is, at this point, the only way to obtain good lower bound on the least singular values of random matrices when the ensemble is discrete (see also [42, 43, 53] for more results and discussion).”
Intersection bounds: estimation and inference (2009, unknown): “…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).”
On the hyperplane conjecture for random convex sets (2006, background): “We remark in passing that in the Bernoulli case the probability of K or T to be degenerate was known before [ 23 ].”
The circular law for random matrices (2007, methodology): “) These bounds are based on the results obtained by Rudelson and Vershynin in [18].”
Large ball probabilities, Gaussian comparison and anti-concentration (2017, unknown): “We refer the interested reader to Rudelson and Vershynin (2008), G¨otze and Zaitsev (2016).”
No-gaps delocalization for general random matrices (2015, methodology): “Our general approach to invertibility follows the method developed by the authors in [23, 25], see also [26].”
Singularity of random Bernoulli matrices (2018, methodology): “The approach that we use in this paper is partially based on the methods used in [13] (and in [9]), while the principal difference lies in estimating anticoncentration properties of random sums.”
Spectrum of Non-Hermitian Heavy Tailed Random Matrices (2010, methodology): “Such lower bounds on the smallest singular value of random matrices were developed in the recent years by using Littlewood-Offord type problems, as in [48, 49] and [45].”
Harmless interpolation of noisy data in regression (2019, background): “It is well-known that the behavior of the minimum singular value of a random matrix with iid Gaussian entries is very diﬀerent when the matrix is approximately square – a “hard-edge" phenomenon arises [21,22] and the minimum singular value actually exhibits heavy-tailed behavior [23].”