Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer

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 $\mathrm{\parallel }{\sum }_i{s}_i{H}_i\mathrm{\parallel }\le 13\mathrm{\parallel }{\sum }_i{H}_i^2{\mathrm{\parallel }}^{1\mathrm{/}2}$. As a corollary, for vectors $v_i$ with ${\sum }_i{v}_i{v}_i^{\ast }=I$ and $\mathrm{\parallel }{v}_i{\mathrm{\parallel }}^2\le \delta$, the signs yield a partition $[N]=S_1\cup S_2$ such that each part satisfies $\mathrm{\parallel }{\sum }_{i\in S_j}{v}_i{v}_i^{\ast }-\frac{I}{2}\mathrm{\parallel }\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{K}\mathsf{S}}_2$ formulation, with a universal constant.