On the Spielman-Teng Conjecture
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912180051378176 |
|---|---|
| author | Sah, Ashwin Sahasrabudhe, Julian Sawhney, Mehtaab |
| author_facet | Sah, Ashwin Sahasrabudhe, Julian Sawhney, Mehtaab |
| contents | Let $M$ be an $n\times n$ matrix with iid subgaussian entries with mean $0$ and variance $1$ and let $σ_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 \leq \varepsilon \ll 1$. This resolves, up to a $1+o(1)$ factor, a seminal conjecture of Spielman and Teng. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_20308 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Spielman-Teng Conjecture Sah, Ashwin Sahasrabudhe, Julian Sawhney, Mehtaab Probability Combinatorics Let $M$ be an $n\times n$ matrix with iid subgaussian entries with mean $0$ and variance $1$ and let $σ_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 \leq \varepsilon \ll 1$. This resolves, up to a $1+o(1)$ factor, a seminal conjecture of Spielman and Teng. |
| title | On the Spielman-Teng Conjecture |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2405.20308 |