Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input

The Matrix Spencer conjecture asserts that for all symmetric matrices $A_1,\dots ,A_n\in {\mathbb{R}}^{n\times n}$ with $\mathrm{\parallel }{A}_i\mathrm{\parallel }\le 1$ there are signs ${\epsilon }_1,\dots ,{\epsilon }_n\in \{-1,1\}$ with $\mathrm{\parallel }{\sum }_{i=1}^n{\epsilon }_i{A}_i\mathrm{\parallel }=O(\sqrt{n})$. Random signs give only the matrix-concentration bound $O(\sqrt{n\log n})$, and the conjecture was known only under rank, block-diagonal, or Frobenius-norm restrictions. We prove it: a signing of discrepancy below $8\sqrt{n}$ always exists. We also give a randomized algorithm that finds a signing of discrepancy below $12\sqrt{n}$ with failure probability at most $p$ using $n^{3+o(1)}\mathrm{polylog}(1\mathrm{/}p)$ arithmetic operations in the real-arithmetic model, which matches the size $n^3$ of the dense input up to subpolynomial factors. The existence proof is a partial-coloring argument with one new estimate: a hereditary Gaussian small-ball bound for the spectral body $\{x\in {\mathbb{R}}^n:\mathrm{\parallel }{\sum }_i{x}_i{A}_i\mathrm{\parallel }\le R\}$, proved by interpolating a log-partition function from a diagonal model to the noncommutative one under a matrix-weighted Poincaré inequality. Proving the conjecture and bringing the constant below $8$ are different problems. The partial-coloring argument loses a large factor twice, when it turns Gaussian measure into signs through a union bound and when it proves the small-ball estimate at a radius far larger than necessary. We remove the first loss by a lossless coding of Gaussian measure into signs and the second by smooth spectral barriers with certified coefficients. The algorithms project Gaussian points onto a smoothed version of the spectral body, whose derivatives are traces against one Gibbs matrix. Four successively cheaper ways of maintaining that matrix bring the running time down to $n^{3+o(1)}$.