arXiv preprint ·
Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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)}$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer
Resolution-Independent Analysis of Encoder--Decoder Operator Learning via Limiting Kernels
A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture
Nonmaximal sums of maximally monotone operators under Rockafellar's constraint qualification
Toscani-Fourier Distance on Probability Measures: Wasserstein Control, Topological Equivalence on Model Classes, and Duality
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.