Four Deviations Suffice for Rank 1 Matrices

We prove a matrix discrepancy bound that strengthens the famous Kadison-Singer result of Marcus, Spielman, and Srivastava. Consider any independent scalar random variables ${\xi }_1,\dots ,{\xi }_n$ with finite support, e.g. $\{\pm 1\}$ or $\{0,1\}$-valued random variables, or some combination thereof. Let $u_1,\dots ,u_n\in {\mathbb{C}}^m$ and $${\sigma }^2=\parallel \sum _{i=1}^n\text{Var}[{\xi }_i](u_i{u}_i^{\ast }{)}^2\parallel \mathrm{.}$$ Then there exists a choice of outcomes ${\epsilon }_1,\dots ,{\epsilon }_n$ in the support of ${\xi }_1,\dots ,{\xi }_n$ s.t. $$\parallel \sum _{i=1}^n\mathbb{E}[{\xi }_i]u_i{u}_i^{\ast }-\sum _{i=1}^n{\epsilon }_i{u}_i{u}_i^{\ast }\parallel \le 4\sigma \mathrm{.}$$ A simple consequence of our result is an improvement of a Lyapunov-type theorem of Akemann and Weaver.