On the smoothed analysis of the smallest singular value with discrete noise

Abstract

Let $A$ be an $n\times n$ real matrix, and let $M$ be an $n\times n$ random matrix whose entries are i.i.d sub-Gaussian random variables with mean $0$ and variance $1$. We make two contributions to the study of $s_n(A+M)$, the smallest singular value of $A+M$. (1) We show that for all $\epsilon \ge 0$, $$\mathbb{P}[s_n(A+M)\le \epsilon ]=O(\epsilon \sqrt{n})+2e^{-\Omega (n)},$$ provided only that $A$ has $\Omega (n)$ singular values which are $O(\sqrt{n})$. This extends a well-known result of Rudelson and Vershynin, which requires all singular values of $A$ to be $O(\sqrt{n})$. (2) We show that any bound of the form $$\underset{\Vert A\Vert \le n^{C_1}}{\sup }\mathbb{P}[s_n(A+M)\le n^{-C_3}]\le n^{-C_2}$$ must have $C_3=\Omega (C_1\sqrt{C_2})$. This complements a result of Tao and Vu, who proved such a bound with $C_3=O(C_1{C}_2+C_1+1)$, and counters their speculation of possibly taking $C_3=O(C_1+C_2)$.

15 pages; comments welcome!