Polynomial Time Algorithms for the Kadison-Singer Problem

Marcus, Spielman, and Srivastava [MSS15] established the existence of Kadison–Singer partitions. We provide polynomial-time algorithms for the Kadison–Singer problem. For Hermitian matrices $A_1,\dots ,A_m\in {\mathbb{C}}^{n\times n}$ of rank at most one, we give two algorithms that find signs $\sigma \in \{\pm 1{\}}^m$ satisfying $\mathrm{\parallel }{\sum }_i{\sigma }_i{A}_i\mathrm{\parallel }\le C\mathrm{\parallel }{\sum }_i{A}_i^2{\mathrm{\parallel }}^{1\mathrm{/}2}$. The deterministic algorithm achieves $C=3.3443$ using $\tilde{O}(m{n}^2+n^{56})$ arithmetic operations. The randomized algorithm achieves $C=4.8628$ using $\tilde{O}(m{n}^2+n^{5.88})$ arithmetic operations in expectation. For vectors satisfying ${\sum }_i{a}_i{a}_i^{\ast }=I$ and $\mathrm{\parallel }{a}_i{\mathrm{\parallel }}^2\le \alpha$, the algorithms yield partitions $[m]=I_1\cup I_2$ satisfying $\mathrm{\parallel }{\sum }_{i\in I_j}{a}_i{a}_i^{\ast }-I\mathrm{/}2\mathrm{\parallel }\le (C\mathrm{/}2)\sqrt{\alpha }$ for $j=1,2$.