The Littlewood-Offord problem and invertibility of random matrices

DOI10.1016/J.AIM.2008.01.010MaRDI QIDQ2483181zbMATH OpenOpenAlexFDO

Authors Mark Rudelson, Roman Vershynin

Publication date 28 April 2008

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0703503

zbMATH Keywords

condition numberGaussian matricesrandom matricessingular valuessmall ball probability

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52)

Abstract: We prove two basic conjectures on the distribution of the smallest singular value of random n times 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 of 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.

Recommendations

• Inverse Littlewood-Offord problems and the singularity of random symmetric matrices
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Quantitative invertibility of random matrices: a combinatorial perspective
• Invertibility of symmetric random matrices
• Invertibility of random matrices: Unitary and orthogonal perturbations
• The asymptotic probability that a random biased matrix is invertible
• Invertibility of random matrices: norm of the inverse
• On a problem of Farrell and Vershynin in random matrix theory
• Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality
• Distribution of the generalised inverse of a random matrix and its applications

Cites work

• A note on the largest eigenvalue of a large dimensional sample covariance matrix
• A note on universality of the distribution of the largest eigenvalues in certain sample covariance matrices
• Circular law, extreme singular values and potential theory
• Compressed sensing
• Condition numbers of random matrices
• Eigenvalues and Condition Numbers of Random Matrices
• Estimates for the concentration function of combinatorial number theory and probability
• Gaussian processes: Inequalities, small ball probabilities and applications
• Global versus local asymptotic theories of finite-dimensional normed spaces
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 520220 (Why is no real title available?)
• scientific article; zbMATH DE number 1962932 (Why is no real title available?)
• scientific article; zbMATH DE number 3232871 (Why is no real title available?)
• scientific article; zbMATH DE number 3245540 (Why is no real title available?)
• scientific article; zbMATH DE number 3299651 (Why is no real title available?)
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Invertibility of random matrices: norm of the inverse
• Local operator theory, random matrices and Banach spaces.
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• On a lemma of Littlewood and Offord
• On random ±1 matrices: Singularity and determinant
• On subspaces spanned by random selections of 1 vectors
• On the distribution of additive arithmetic functions
• On the efficiency of algorithms of analysis
• On the Kolmogorov-Rogozin inequality for the concentration function
• On the limit of the largest eigenvalue of the large dimensional sample covariance matrix
• On the Probability That a Random ± 1-Matrix Is Singular
• On the singularity probability of random Bernoulli matrices
• Smallest singular value of random matrices and geometry of random polytopes
• Solution of the Littlewood-Offord problem in high dimensions
• Some estimates of norms of random matrices
• Über ein Problem von Erdös und Moser

Cited in

(only showing first 100 items - show all)

• A randomized Kaczmarz algorithm with exponential convergence
• Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries
• Lower bounds for the smallest singular value of structured random matrices
• Reciprocal graphical models for integrative gene regulatory network analysis
• The method of perpendiculars of finding estimates from below for minimal singular eigenvalues of random matrices
• Random matrices: overcrowding estimates for the spectrum
• Asymptotic Lyapunov exponents for large random matrices
• Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
• The spectral gap of dense random regular graphs
• The smallest singular value of a shifted d-regular random square matrix
• Circular law for the sum of random permutation matrices
• Row products of random matrices
• On the rate of decay of concentration functions of \(n\)-fold convolutions of probability distributions
• Toward the history of the Saint St. Petersburg school of probability and statistics. I: Limit theorems for sums of independent random variables
• Bilinear and quadratic variants on the Littlewood-Offord problem
• Random matrices: universality of ESDs and the circular law
• Universality and least singular values of random matrix products: a simplified approach
• A nonuniform Littlewood-Offord inequality for all norms
• Sparse random matrices have simple spectrum
• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• On the singularity of random symmetric matrices
• The smallest singular value of inhomogeneous square random matrices
• Recent progress in combinatorial random matrix theory
• Inhomogeneous circular law for correlated matrices
• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
• Non-asymptotic results for singular values of Gaussian matrix products
• Universality of the least singular value for the sum of random matrices
• Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
• On the permanent of a random symmetric matrix
• The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding
• Invertibility of adjacency matrices for random d-regular graphs
• Tail bounds for gaps between eigenvalues of sparse random matrices
• Spectrum and pseudospectrum for quadratic polynomials in Ginibre matrices
• The least singular value of the general deformed Ginibre ensemble
• Spectrum of heavy-tailed elliptic random matrices
• Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices
• On eigenvalue distributions of large autocovariance matrices
• Random integral matrices: universality of surjectivity and the cokernel
• Singularity of discrete random matrices
• Singularity of sparse Bernoulli matrices
• Salem-Zygmund inequality for locally sub-Gaussian random variables, random trigonometric polynomials, and random circulant matrices
• Smoothed analysis for tensor methods in unsupervised learning
• Zero-free neighborhoods around the unit circle for Kac polynomials
• On the complexity of the Plantinga-Vegter algorithm
• Smallest singular value and limit eigenvalue distribution of a class of non-Hermitian random matrices with statistical application
• On delocalization of eigenvectors of random non-Hermitian matrices
• Concentration inequalities for random tensors
• On block Gaussian sketching for the Kaczmarz method
• A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
• The circular law for random regular digraphs
• Large ball probabilities, Gaussian comparison and anti-concentration
• The circular law for sparse non-Hermitian matrices
• Small-deviation inequalities for sums of random matrices
• Random matrices: universality of local spectral statistics of non-Hermitian matrices
• Comparison and anti-concentration bounds for maxima of Gaussian random vectors
• On the concentration of random multilinear forms and the universality of random block matrices
• Invertibility of random matrices: norm of the inverse
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence
• The sparse circular law under minimal assumptions
• Circular law theorem for random Markov matrices
• Random matrices: law of the determinant
• Random doubly stochastic matrices: the circular law
• Bounds on the concentration function in terms of the Diophantine approximation
• The smallest singular value of random rectangular matrices with no moment assumptions on entries
• Optimal lower bound on the least singular value of the shifted Ginibre ensemble
• Smoothed analysis of symmetric random matrices with continuous distributions
• On a condition number of general random polynomial systems
• Circular law for random matrices with exchangeable entries
• Condition number of a square matrix with i.i.d. columns drawn from a convex body
• On the Littlewood-Offord problem
• On a Conjecture of Godsil Concerning Controllable Random Graphs
• Berry-Esseen bounds and multivariate limit theorems for functionals of Rademacher sequences
• A sharp inverse Littlewood-Offord theorem
• Adjacency matrices of random digraphs: singularity and anti-concentration
• Upper bound for intermediate singular values of random matrices
• Smooth analysis of the condition number and the least singular value
• Non-abelian Littlewood-Offord inequalities
• Hafnians, perfect matchings and Gaussian matrices
• Book Review: A mathematical introduction to compressive sensing
• Quantitative invertibility of random matrices: a combinatorial perspective
• Local laws for non-Hermitian random matrices and their products
• Aspects of large random Markov kernels
• On minimal singular values of random matrices with correlated entries
• Singular values of Gaussian matrices and permanent estimators
• On the volume of caps and bounding the mean-width of an isotropic convex body
• Smallest singular value of a random rectangular matrix
• Improved approximation of linear threshold functions
• Local circular law for random matrices
• The local circular law. II: The edge case
• Inverse Littlewood-Offord problems and the singularity of random symmetric matrices
• Around the circular law
• Complex random matrices have no real eigenvalues
• Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
• A well-tempered landscape for non-convex robust subspace recovery
• Eigenvectors of random matrices of symmetric entry distributions
• The local circular law. III: General case
• Circular law for random block band matrices with genuinely sublinear bandwidth
• The limit of the smallest singular value of random matrices with i.i.d. entries
• Surjectivity of near-square random matrices

This page was built for publication: The Littlewood-Offord problem and invertibility of random matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2483181)