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

Understand

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 \geq 0$, $$\mathbb{P}[s_n(A + M) \leq \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})$.