Matrix anti-concentration inequalities with applications

We provide a polynomial lower bound on the minimum singular value of an m× m random matrix M with jointly Gaussian entries, under a polynomial bound on the matrix norm and a global small-ball probability bound inf_x,y∈ Sm-1mathbbPleft(left|x^* M yright|>m-O(1)right)≥ frac12. With the additional assumption that M is self-adjoint, the global small-ball probability bound can be replaced by a weaker version. We establish two matrix anti-concentration inequalities, which lower bound the minimum singular values of the sum of independent positive semidefinite self-adjoint matrices and the linear combination of independent random matrices with independent Gaussian coefficients. Both are under a global small-ball probability assumption. As a major application, we prove a better singular value bound for the Krylov space matrix, which leads to a faster and simpler algorithm for solving sparse linear systems. Our algorithm runs in tildeOleft(n^frac3ω-4ω-1right)=O(n2.2716) time where ω<2.37286 is the matrix multiplication exponent, improving on the previous fastest one in tildeOleft(n^frac5ω-4ω+1right)=O(n2.33165) time by Peng and Vempala.