Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer

Abstract

We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots ,H_N$ of rank at most one, finds signs $s\in \{\pm 1{\}}^N$ with $\Vert {\sum }_i{s}_i{H}_i\Vert \le 13\Vert {\sum }_i{H}_i^2{\Vert }^{1/2}$. As a corollary, for vectors $v_i$ with ${\sum }_i{v}_i{v}_i^{\ast }=I$ and $\Vert v_i{\Vert }^2\le \delta$, the signs yield a partition $[N]=S_1\cup S_2$ such that each part satisfies $\Vert {\sum }_{i\in S_j}{v}_i{v}_i^{\ast }-\frac{I}{2}\Vert \le \frac{13}{2}\sqrt{\delta }$ for $j=1,2$. This gives a deterministic polynomial-time algorithm for the Kadison--Singer problem, in Weaver's equivalent discrepancy-theoretic ${\mathsf{KS}}_2$ formulation, with a universal constant.