The smallest singular value of inhomogeneous square random matrices

DOI10.1214/20-AOP1481MaRDI QIDQ2039434zbMATH OpenOpenAlexFDO

Authors Galyna V. Livshyts, Konstantin E. Tikhomirov, Roman Vershynin

Publication date 2 July 2021

Published in The Annals of Probability (Search for Journal in Brave)

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

zbMATH Keywords

Littlewood-Offord problemrandom matrices

Mathematics Subject Classification ID

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

Abstract: We show that for an $nimesn$ random matrix $A$ with independent uniformly anti-concentrated entries, such that $mathbbE||A|{|}_{HS}^{2}leqK{n}^2$, the smallest singular value $sigm{a}_n(A)$ of $A$ satisfies ${\displaystyle }$ Pleft( sigma_n(A)leq frac{varepsilon}{sqrt{n}} ight) leq Cvarepsilon+2e^{-cn},quad varepsilon ge 0. ${\displaystyle }$ This extends earlier results of Rudelson and Vershynin, and Rebrova and Tikhomirov by removing the assumption of mean zero and identical distribution of the entries across the matrix, as well as the recent result of Livshyts, where the matrix was required to have i.i.d. rows. Our model covers "inhomogeneus" matrices allowing different variances of the entries, as long as the sum of the second moments is of order $O(n^2)$. In the past advances, the assumption of i.i.d. rows was required due to lack of Littlewood--Offord--type inequalities for weighted sums of non-i.i.d. random variables. Here, we overcome this problem by introducing the Randomized Least Common Denominator (RLCD) which allows to study anti-concentration properties of weighted sums of independent but not identically distributed variables. We construct efficient nets on the sphere with lattice structure, and show that the lattice points typically have large RLCD. This allows us to derive strong anti-concentration properties for the distance between a fixed column of $A$ and the linear span of the remaining columns, and prove the main result.

Recommendations

• Smallest singular value of random matrices with independent columns
• The smallest singular value of random rectangular matrices with no moment assumptions on entries
• The Littlewood-Offord problem and invertibility of random matrices
• Smallest singular value of sparse random matrices
• The least singular value of a random square matrix is O\((n ^{- 1/2})\)

Cites work

• An upper bound on the smallest singular value of a square random matrix
• Condition numbers of random matrices
• Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries
• Delocalization of eigenvectors of random matrices with independent entries
• Eigenvalues and Condition Numbers of Random Matrices
• Entropy numbers of diagonal operators between symmetric Banach spaces
• scientific article; zbMATH DE number 1559589 (Why is no real title available?)
• scientific article; zbMATH DE number 1405893 (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
• Lower bounds for the smallest singular value of structured random matrices
• Necessary and sufficient conditions for almost sure convergence of the largest eigenvalue of a Wigner matrix
• Numerical inverting of matrices of high order
• On random ±1 matrices: Singularity and determinant
• On the Kolmogorov-Rogozin inequality for the concentration function
• On the Probability That a Random ± 1-Matrix Is Singular
• On the singular values of random matrices
• On the singularity probability of discrete random matrices
• On the singularity probability of random Bernoulli matrices
• Random matrices: The distribution of the smallest singular values
• Singularity of random Bernoulli matrices
• Smallest singular value of a random rectangular matrix
• Smallest singular value of random matrices and geometry of random polytopes
• Smallest singular value of sparse random matrices
• Spectral norm of products of random and deterministic matrices
• The limit of the smallest singular value of random matrices with i.i.d. entries
• The Littlewood-Offord problem and invertibility of random matrices
• The Lower Bound for Koldobsky’s Slicing Inequality via Random Rounding
• The smallest singular value of random rectangular matrices with no moment assumptions on entries

Cited in

(29)

• Universality and least singular values of random matrix products: a simplified approach
• The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding
• Random matrix theory and its applications
• Singularity of discrete random matrices
• Singularity of sparse Bernoulli matrices
• Zero-free neighborhoods around the unit circle for Kac polynomials
• On sparse random combinatorial matrices
• Smallest singular value and limit eigenvalue distribution of a class of non-Hermitian random matrices with statistical application
• Least singular value and condition number of a square random matrix with i.i.d. rows
• Smallest singular value of random matrices and geometry of random polytopes
• Quantitative invertibility of random matrices: a combinatorial perspective
• A note on the universality of ESDs of inhomogeneous random matrices
• A measure concentration effect for matrices of high, higher, and even higher dimension
• Random Toeplitz matrices: The condition number under high stochastic dependence
• On the smallest singular value of symmetric random matrices
• The smallest singular value of a shifted random matrix
• On the largest and the smallest singular value of sparse rectangular random matrices
• Quantitative invertibility of non-Hermitian random matrices
• The least singular value of a random symmetric matrix
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Asymptotic geometric analysis: achievements and perspective
• A large deviation inequality for the rank of a random matrix
• The singularity probability of a random symmetric matrix is exponentially small
• Phase transition for the bottom singular vector of rectangular random matrices
• An upper bound on the smallest singular value of a square random matrix
• An upper bound on the smallest singular value of dense random combinatorial matrices
• Regional Stability and New Eigenvalue Perturbation Bounds
• Smallest singular value of random matrices with independent columns
• The least singular value of a random square matrix is O\((n ^{- 1/2})\)

This page was built for publication: The smallest singular value of inhomogeneous square random matrices

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