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 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 selfadjoint 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 Õ n 3ω-4 ω-1 = O(n 2.2716 ) time where ω < 2.37286 is the matrix multiplication exponent, improving on the previous fastest one in Õ n 5ω-4 ω+1 = O(n 2.33165 ) time by Peng and Vempala.