Polynomial Time Algorithms for the Kadison-Singer Problem

Abstract

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 $\Vert {\sum }_i{\sigma }_i{A}_i\Vert \le C\Vert {\sum }_i{A}_i^2{\Vert }^{1/2}$. The deterministic algorithm achieves $C=3.3443$ using $\tilde{O}(m{n}^2+n^{4.75})$ arithmetic operations. The randomized algorithm achieves $C=4.8628$ using $\tilde{O}(m{n}^2+n^{3.58})$ arithmetic operations in expectation. For vectors satisfying ${\sum }_i{a}_i{a}_i^{\ast }=I$ and $\Vert a_i{\Vert }^2\le \alpha$, the algorithms yield partitions $[m]=I_1\cup I_2$ satisfying $\Vert {\sum }_{i\in I_j}{a}_i{a}_i^{\ast }-I/2\Vert \le (C/2)\sqrt{\alpha }$ for $j=1,2$.