The smallest singular value of inhomogeneous square random matrices

DOI10.1214/20-AOP1481zbMATH Open1467.60010arXiv1909.04219OpenAlexW3150590775MaRDI QIDQ2039434FDOQ2039434

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)

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.

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

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})\)

zbMATH Keywords

random matricesLittlewood-Offord problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (26)

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

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)