On the Spielman-Teng Conjecture

Abstract

Let $M$ be an $n\times n$ matrix with iid subgaussian entries with mean $0$ and variance $1$ and let $\ddot{I}{ƒ}_n(M)$ denote the least singular value of $M$. We prove that \[\mathbb{P}\big( σ_{n}(M) \leq \varepsilon n^{-1/2} \big) = (1+o(1)) \varepsilon + e^{-Ω(n)}\] for all $0\le \epsilon \ll 1$. This resolves, up to a $1+o(1)$ factor, a seminal conjecture of Spielman and Teng.

29 pages