The Littlewood-Offord problem and invertibility of random matrices

DOI10.1016/j.aim.2008.01.010zbMath1139.15015arXivmath/0703503OpenAlexW2081131431MaRDI QIDQ2483181

R. V. Vershinin, M. V. Rudel'son

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

random matricescondition numbersingular valuessmall ball probabilityGaussian matrices

Mathematics Subject Classification ID

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

Related Items

Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries ⋮ Singularity of discrete random matrices ⋮ Lower bounds for the smallest singular value of structured random matrices ⋮ Singularity of sparse Bernoulli matrices ⋮ On the Littlewood-Offord problem ⋮ Berry-Esseen bounds and multivariate limit theorems for functionals of Rademacher sequences ⋮ Reciprocal graphical models for integrative gene regulatory network analysis ⋮ On the hyperplane conjecture for random convex sets ⋮ The smallest singular value of random rectangular matrices with no moment assumptions on entries ⋮ The method of perpendiculars of finding estimates from below for minimal singular eigenvalues of random matrices ⋮ Salem-Zygmund inequality for locally sub-Gaussian random variables, random trigonometric polynomials, and random circulant matrices ⋮ Adjacency matrices of random digraphs: singularity and anti-concentration ⋮ Upper bound for intermediate singular values of random matrices ⋮ Smoothed analysis for tensor methods in unsupervised learning ⋮ Circular law, extreme singular values and potential theory ⋮ Non-abelian Littlewood-Offord inequalities ⋮ Hafnians, perfect matchings and Gaussian matrices ⋮ Zero-free neighborhoods around the unit circle for Kac polynomials ⋮ Random matrices: overcrowding estimates for the spectrum ⋮ On the complexity of the Plantinga-Vegter algorithm ⋮ Improved approximation of linear threshold functions ⋮ Erratum to: Outliers in the spectrum of iid matrices with bounded rank perturbations ⋮ Optimal lower bound on the least singular value of the shifted Ginibre ensemble ⋮ Smallest singular value and limit eigenvalue distribution of a class of non-Hermitian random matrices with statistical application ⋮ On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence ⋮ On delocalization of eigenvectors of random non-Hermitian matrices ⋮ The sparse circular law under minimal assumptions ⋮ Circular law for noncentral random matrices ⋮ Local circular law for random matrices ⋮ The local circular law. II: The edge case ⋮ Delocalization of eigenvectors of random matrices with independent entries ⋮ Circular law theorem for random Markov matrices ⋮ Multivariate estimates for the concentration functions of weighted sums of independent, identically distributed random variables ⋮ Optimal inverse Littlewood-Offord theorems ⋮ Around the circular law ⋮ Concentration inequalities for random tensors ⋮ Asymptotic Lyapunov exponents for large random matrices ⋮ Limiting empirical singular value distribution of restrictions of discrete Fourier transform matrices ⋮ Random matrices: law of the determinant ⋮ Bilinear and quadratic variants on the Littlewood-Offord problem ⋮ Spectrum of non-Hermitian heavy tailed random matrices ⋮ Random matrices: universality of ESDs and the circular law ⋮ On block Gaussian sketching for the Kaczmarz method ⋮ Random doubly stochastic matrices: the circular law ⋮ Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions ⋮ The spectral gap of dense random regular graphs ⋮ The local circular law. III: General case ⋮ A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian ⋮ Smallest singular value of random matrices with independent columns ⋮ The least singular value of a random square matrix is O\((n ^{- 1/2})\) ⋮ The smallest singular value of a shifted $d$-regular random square matrix ⋮ Bounds on the concentration function in terms of the Diophantine approximation ⋮ The limit of the smallest singular value of random matrices with i.i.d. entries ⋮ Universality and least singular values of random matrix products: a simplified approach ⋮ Small ball estimates for quasi-norms ⋮ A bound for the maximal probability in the Littlewood-Offord problem ⋮ On the singularity of adjacency matrices for random regular digraphs ⋮ Inverse Littlewood-Offord problems for quasi-norms ⋮ Circular law for the sum of random permutation matrices ⋮ Invertibility of sparse non-Hermitian matrices ⋮ Random matrices: tail bounds for gaps between eigenvalues ⋮ Row products of random matrices ⋮ On the rate of decay of concentration functions of \(n\)-fold convolutions of probability distributions ⋮ A nonuniform Littlewood-Offord inequality for all norms ⋮ Random matrices: The distribution of the smallest singular values ⋮ Spectral norm of products of random and deterministic matrices ⋮ The circular law for random matrices ⋮ An upper bound on the smallest singular value of a square random matrix ⋮ Sparse random matrices have simple spectrum ⋮ Sharp transition of the invertibility of the adjacency matrices of sparse random graphs ⋮ Toward the history of the Saint St. Petersburg school of probability and statistics. I: Limit theorems for sums of independent random variables ⋮ No-gaps delocalization for general random matrices ⋮ 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 ⋮ The circular law for random regular digraphs ⋮ 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 ⋮ A randomized Kaczmarz algorithm with exponential convergence ⋮ 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 ⋮ Convergence and asymptotic approximations to universal distributions in probability ⋮ Large ball probabilities, Gaussian comparison and anti-concentration ⋮ Spectrum and pseudospectrum for quadratic polynomials in Ginibre matrices ⋮ The circular law for sparse non-Hermitian matrices ⋮ The least singular value of the general deformed Ginibre ensemble ⋮ Spectrum of heavy-tailed elliptic random matrices ⋮ Random matrix products: universality and least singular values ⋮ Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices ⋮ Small-deviation inequalities for sums of random matrices ⋮ On eigenvalue distributions of large autocovariance 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 ⋮ Random integral matrices: universality of surjectivity and the cokernel ⋮ Condition number of a square matrix with i.i.d. columns drawn from a convex body ⋮ Singularity of sparse random matrices: simple proofs ⋮ On the smallest singular value of symmetric random matrices ⋮ Smooth analysis of the condition number and the least singular value ⋮ Random sections of ellipsoids and the power of random information ⋮ On minimal singular values of random matrices with correlated entries ⋮ Book Review: A mathematical introduction to compressive sensing ⋮ Singular values of Gaussian matrices and permanent estimators ⋮ From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices ⋮ Singularity of random symmetric matrices revisited ⋮ Random Toeplitz matrices: The condition number under high stochastic dependence ⋮ A note on the universality of ESDs of inhomogeneous random matrices ⋮ Quantitative invertibility of random matrices: a combinatorial perspective ⋮ Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture ⋮ On a Conjecture of Godsil Concerning Controllable Random Graphs ⋮ The smallest singular value of a shifted random matrix ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ On the largest and the smallest singular value of sparse rectangular random matrices ⋮ Quantitative invertibility of non-Hermitian random matrices ⋮ Large deviations in random latin squares ⋮ Spectral measure of empirical autocovariance matrices of high-dimensional Gaussian stationary processes ⋮ The least singular value of a random symmetric matrix ⋮ Entropic hardness of Module-LWE from module-NTRU ⋮ Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022 ⋮ On the smoothed analysis of the smallest singular value with discrete noise ⋮ A discrete variation of the Littlewood-Offord problem ⋮ Second- and higher-order Gaussian anticoncentration inequalities and error bounds in Slepian's comparison theorem ⋮ Complex random matrices have no real eigenvalues ⋮ Small Ball Probability for the Condition Number of Random Matrices ⋮ Eigenvector delocalization for non‐Hermitian random matrices and applications ⋮ Structure of eigenvectors of random regular digraphs ⋮ Invertibility of random matrices: Unitary and orthogonal perturbations ⋮ Eigenvectors of random matrices of symmetric entry distributions ⋮ Invertibility of symmetric random matrices ⋮ Anticoncentration versus the Number of Subset Sums ⋮ Spectrum of Markov Generators on Sparse Random Graphs ⋮ On the volume of caps and bounding the mean-width of an isotropic convex body ⋮ Smoothed analysis of symmetric random matrices with continuous distributions ⋮ On a condition number of general random polynomial systems ⋮ SINGULARITY OF RANDOM SYMMETRIC MATRICES—A COMBINATORIAL APPROACH TO IMPROVED BOUNDS ⋮ A sharp inverse Littlewood-Offord theorem ⋮ Eigenvectors of random graphs: Nodal Domains ⋮ An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs ⋮ Circular law for random block band matrices with genuinely sublinear bandwidth ⋮ Circular law for random matrices with exchangeable entries ⋮ A Combinatorial Approach to Small Ball Inequalities for Sums and Differences ⋮ Local laws for non-Hermitian random matrices and their products ⋮ Aspects of large random Markov kernels ⋮ Smallest singular value of a random rectangular matrix ⋮ On global universality for zeros of random polynomials ⋮ A Well-Tempered Landscape for Non-convex Robust Subspace Recovery ⋮ Surjectivity of near-square random matrices ⋮ Resilience of the rank of random matrices ⋮ Arak Inequalities for Concentration Functions and the Littlewood--Offord Problem ⋮ On Approximating Matrix Norms in Data Streams ⋮ Smoothed analysis for the condition number of structured real polynomial systems ⋮ The probabilistic estimates on the largest and smallest $q$-singular values of random matrices ⋮ Controllability of Network Opinion in Erdös--Rényi Graphs Using Sparse Control Inputs ⋮ Entropy Inequalities for Sums in Prime Cyclic Groups ⋮ Some new results in random matrices over finite fields ⋮ Unnamed Item ⋮ Large-deviation asymptotics of condition numbers of random matrices ⋮ Rate of convergence to the Circular Law via smoothing inequalities for log-potentials ⋮ The strong circular law: A combinatorial view ⋮ Circular law for random matrices with unconditional log-concave distribution ⋮ Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors ⋮ Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial

Cites Work

• Circular law, extreme singular values and potential theory
• On the limit of the largest eigenvalue of the large dimensional sample covariance matrix
• A note on the largest eigenvalue of a large dimensional sample covariance matrix
• On subspaces spanned by random selections of \(\pm 1\) vectors
• Solution of the Littlewood-Offord problem in high dimensions
• Condition numbers of random matrices
• Global versus local asymptotic theories of finite-dimensional normed spaces
• A note on universality of the distribution of the largest eigenvalues in certain sample covariance matrices
• Invertibility of random matrices: norm of the inverse
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Smallest singular value of random matrices and geometry of random polytopes
• On random ±1 matrices: Singularity and determinant
• On the singularity probability of random Bernoulli matrices
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• On the efficiency of algorithms of analysis
• Eigenvalues and Condition Numbers of Random Matrices
• Estimates for the concentration function of combinatorial number theory and probability
• Some estimates of norms of random matrices
• On the Probability That a Random ± 1-Matrix Is Singular
• Über ein Problem von Erdös und Moser
• On the Kolmogorov-Rogozin inequality for the concentration function
• On the distribution of additive arithmetic functions
• On a lemma of Littlewood and Offord
• Compressed sensing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item