Quantitative invertibility of random matrices: a combinatorial perspective

DOI10.19086/DA.27994MaRDI QIDQ3382245zbMATH OpenOpenAlexFDO

Authors Vishesh Jain

Publication date 20 September 2021

Published in discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

inverse Littlewood-Offord problemleast singular valuesmoothed analysis

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Theory of matrix inversion and generalized inverses (15A09) Random matrices (algebraic aspects) (15B52)

Abstract: We study the lower tail behavior of the least singular value of an $nimesn$ random matrix $M_n:=M+N_n$, where $M$ is a fixed complex matrix with operator norm at most $exp(n^c)$ and $N_n$ is a random matrix, each of whose entries is an independent copy of a complex random variable with mean $0$ and variance $1$. Motivated by applications, our focus is on obtaining bounds which hold with extremely high probability, rather than on the least singular value of a typical such matrix. This setting has previously been considered in a series of influential works by Tao and Vu, most notably in connection with the strong circular law, and the smoothed analysis of the condition number, and our results improve upon theirs in two ways: (i) We are able to handle $|M|=O(exp(n^c))$, whereas the results of Tao and Vu are applicable only for $M=O(extpoly(n))$. (ii) Even for $M=O(extpoly(n))$, we are able to extract more refined information -- for instance, our results show that for such $M$, the probability that $M_n$ is singular is $O(exp(-n^c))$, whereas even in the case when $xi$ is a Bernoulli random variable, the results of Tao and Vu only give a bound of the form $O_C(n^{-C})$ for any constant $C>0$. As opposed to all previous works obtaining such bounds with error rate better than $n^{-1}$, our proof makes no use either of the inverse Littlewood--Offord theorems, or of any sophisticated net constructions. Instead, we show how to reduce the problem from the (complex) sphere to (Gaussian) integer vectors, where it is solved directly by utilizing and extending a combinatorial approach to the singularity problem for random discrete matrices, recently developed by Ferber, Luh, Samotij, and the author.

Recommendations

• The strong circular law: A combinatorial view
• On the singularity of random combinatorial matrices
• Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
• Singularity of sparse Bernoulli matrices
• The Littlewood-Offord problem and invertibility of random matrices

Cites work

• A sharp inverse Littlewood-Offord theorem
• Additive combinatorics
• Complex random matrices have no real eigenvalues
• Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries
• Eigenvalues and Condition Numbers of Random Matrices
• Estimates for the concentration function of combinatorial number theory and probability
• scientific article; zbMATH DE number 5485458 (Why is no real title available?)
• scientific article; zbMATH DE number 3230288 (Why is no real title available?)
• scientific article; zbMATH DE number 3245540 (Why is no real title available?)
• scientific article; zbMATH DE number 3099315 (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
• Invertibility via distance for noncentered random matrices with continuous distributions
• No-gaps delocalization for general random matrices
• On a combinatorial conjecture of Erdös
• On a lemma of Littlewood and Offord
• On the counting problem in inverse Littlewood-Offord theory
• On the Kolmogorov-Rogozin inequality for the concentration function
• On the Probability That a Random ± 1-Matrix Is Singular
• On the singularity probability of discrete random matrices
• On the singularity probability of random Bernoulli matrices
• Optimal inverse Littlewood-Offord theorems
• Random matrices: universality of ESDs and the circular law
• Singularity of random Bernoulli matrices
• Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
• Small ball probability, inverse theorems, and applications
• Smallest singular value of random matrices and geometry of random polytopes
• Smooth analysis of the condition number and the least singular value
• Smoothed analysis of algorithms
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Some extensions of the Cauchy-Davenport theorem
• The circular law for random matrices
• The Littlewood-Offord problem and invertibility of random matrices
• The smallest singular value of inhomogeneous square random matrices
• Über ein Problem von Erdös und Moser

Cited in

(8)

• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
• Invertibility of adjacency matrices for random d-regular graphs
• On sparse random combinatorial matrices
• The Littlewood-Offord problem and invertibility of random matrices
• Invertibility of random matrices: Unitary and orthogonal perturbations
• Invertibility of symmetric random matrices
• Quantitative invertibility of non-Hermitian random matrices
• Eigenvalue gaps of random perturbations of large matrices

This page was built for publication: Quantitative invertibility of random matrices: a combinatorial perspective

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