Small ball probability for the condition number of random matrices
Preprint
Abstract
Let $A$ be an $n\times n$ random matrix with i.i.d. entries of zero mean, unit variance and a bounded subgaussian moment. We show that the condition number $s_{\max}(A)/s_{\min}(A)$ satisfies the small ball probability estimate $${\mathbb P}\big\{s_{\max}(A)/s_{\min}(A)\leq n/t\big\}\leq 2\exp(-c t^2),\quad t\geq 1,$$ where $c>0$ may only depend on the subgaussian moment. Although the estimate can be obtained as a combination of known results and techniques, it was not noticed in the literature before. As a key step of the proof, we apply estimates for the singular values of $A$, ${\mathbb P}\big\{s_{n-k+1}(A)\leq ck/\sqrt{n}\big\}\leq 2 \exp(-c k^2), \quad 1\leq k\leq n,$ obtained (under some additional assumptions) by Nguyen.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- The sparse circular law under minimal assumptionsGeometric and Functional Analysis, 2019
- No-gaps delocalization for general random matricesGeometric and Functional Analysis, 2016
- An elementary proof of the restricted invertibility theoremIsrael Journal of Mathematics, 2011
- Smallest singular value of a random rectangular matrixCommunications on Pure and Applied Mathematics, 2009
- The least singular value of a random square matrix isComptes Rendus Mathematique, 2008
- The Littlewood–Offord problem and invertibility of random matricesAdvances in Mathematics, 2008
- Smallest singular value of random matrices and geometry of random polytopesAdvances in Mathematics, 2005
- John's decompositions: Selecting a large partIsrael Journal of Mathematics, 2001
- Condition numbers of random matricesJournal of Complexity, 1991
- Invertibility of ‘large’ submatrices with applications to the geometry of Banach spaces and harmonic analysisIsrael Journal of Mathematics, 1987