Back to Search
Start Over
On the Spielman-Teng Conjecture
- Publication Year :
- 2024
-
Abstract
- Let $M$ be an $n\times n$ matrix with iid subgaussian entries with mean $0$ and variance $1$ and let $\sigma_n(M)$ denote the least singular value of $M$. We prove that \[\mathbb{P}\big( \sigma_{n}(M) \leq \varepsilon n^{-1/2} \big) = (1+o(1)) \varepsilon + e^{-\Omega(n)}\] for all $0 \leq \varepsilon \ll 1$. This resolves, up to a $1+o(1)$ factor, a seminal conjecture of Spielman and Teng.<br />Comment: 27 pages
- Subjects :
- Mathematics - Probability
Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2405.20308
- Document Type :
- Working Paper