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

Source abstract

The Matrix Spencer conjecture asserts that for all symmetric matrices $A_1,\ldots,A_n\in\mathbb{R}^{n\times n}$ with $\|A_i\|\le1$ there are signs $\varepsilon_1,\ldots,\varepsilon_n\in\{-1,1\}$ with $\|\sum_{i=1}^n\varepsilon_iA_i\|=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)}\operatorname{polylog}(1/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:\|\sum_ix_iA_i\|\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)}$.