On the smoothed analysis of the smallest singular value with discrete noise. Issue 2 (12th March 2022)

• Record Type: Journal Article
• Authors: Jain, Vishesh; Sah, Ashwin; Sawhney, Mehtaab
• Is Part Of: Bulletin of the London Mathematical Society. Volume 54:Issue 2(2022)
• Page Start: 369
• Page End: 388
• Publication Date: 2022-03-12
• Subjects: Mathematics -- Periodicals; 510
• DOI: 10.1112/blms.12561
• Languages: English
• ISSNs: 0024-6093

Abstract

Abstract: Let A $A$ be an n × n $n\times n$ real matrix, and let M $M$ be an n × n $n\times n$ random matrix whose entries are independent and identically distributed sub‐Gaussian random variables with mean 0 and variance 1. We make two contributions to the study of s n ( A + M ) $s_n(A+M)$, the smallest singular value of A + M $A+M$ . (1) We show that for all ε ⩾ 0 $\epsilon \geqslant 0$, P [ s n ( A + M ) ⩽ ε ] = O ( ε n ) + 2 e − Ω ( n ), \begin{equation*} \mathbb {P}[s_n(A + M) \leqslant \epsilon ] = O(\epsilon \sqrt {n}) + 2e^{-\Omega (n)}, \end{equation*} provided only that A $A$ has Ω ( n ) $\Omega (n)$ singular values which are O ( n ) $O(\sqrt {n})$ . This extends a well‐known result of Rudelson and Vershynin, which requires all singular values of A $A$ to be O ( n ) $O(\sqrt {n})$ . (2) We show that any bound of the form sup ∥ A ∥ ⩽ n C 1 P [ s n ( A + M ) ⩽ n − C 3 ] ⩽ n − C 2 \begin{equation*} \sup _{\Vert A\Vert \leqslant n^{C_1}}\mathbb {P}[s_n(A+M)\leqslant n^{-C_3}] \leqslant n^{-C_2} \end{equation*} must have C 3 = Ω ( C 1 C 2 ) $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 ) $C_3 = O(C_1C_2 + C_1 + 1)$, and counters their speculation of possibly taking C 3 = O ( C 1 + C 2 ) $C_3 = O(C_1 + C_2)$ .