Smoothed analysis of the least singular value without inverse Littlewood-Offord theory
share
We study the lower tail behavior of the least singular value of an n× n random matrix M_n := M+N_n, where M is a fixed matrix with operator norm at most (n^c) and N_n is a random matrix, each of whose entries is an independent copy of a random variable with mean 0 and variance 1. This has been previously considered in a series of works by Tao and Vu, and our results improve upon theirs in two ways: (i) We are able to handle M = O((n^c)), whereas the results of Tao and Vu are applicable only for M = O(poly(n)). (ii) Even for M = O(poly(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((-n^c)), whereas even in the case when ξ is a Bernoulli random variable, the results of Tao and Vu give a bound of the form O_C(n^-C) for any constant C>0. The main technical novelty of the present work, and the reason for the quantitative improvements, is that unlike all previous works on this problem, we completely avoid the use of the inverse Littlewood-Offord theorems. Instead, we utilize and extend a combinatorial approach to random matrix theory, recently developed by the author along with Ferber, Luh, and Samotij.
READ FULL TEXT