# Matrix anti-concentration inequalities with applications

arXiv: https://arxiv.org/abs/2111.05553 · HTML: https://mlsanity.com/paper/2111.05553/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2021.

## Built on by (most cited first, 6 of 6)

- [Combinatorial Causal Bandits](https://mlsanity.com/paper/2206.01995/) (2022)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Testing Calibration in Nearly-Linear Time](https://mlsanity.com/paper/2402.13187/) (2024)
- [Combinatorial Pure Exploration of Causal Bandits](https://mlsanity.com/paper/2206.07883/) (2022)
- [Combinatorial Causal Bandits without Graph Skeleton](https://mlsanity.com/paper/2301.13392/) (2023)
- [Efficient Certificates of Anti-Concentration Beyond Gaussians](https://mlsanity.com/paper/2405.15084/) (2024)

## Abstract (arXiv)

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.