Four Deviations Suffice for Rank 1 Matrices

Abstract

We prove a matrix discrepancy bound that strengthens the famous Kadison-Singer result of Marcus, Spielman, and Srivastava. Consider any independent scalar random variables $\hat{I}{¾}_1,\dots ,\hat{I}{¾}_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 $$\ddot{I}{ƒ}^2=\Vert \sum _{i=1}^n\text{Var}[\hat{I}{¾}_i](u_i{u}_i^{\ast }{)}^2\Vert .$$ Then there exists a choice of outcomes ${\epsilon }_1,\dots ,{\epsilon }_n$ in the support of $\hat{I}{¾}_1,\dots ,\hat{I}{¾}_n$ s.t. $$\Vert \sum _{i=1}^n\mathbb{E}[\hat{I}{¾}_i]u_i{u}_i^{\ast }-\sum _{i=1}^n{\epsilon }_i{u}_i{u}_i^{\ast }\Vert \le 4\ddot{I}ƒ.$$ A simple consequence of our result is an improvement of a Lyapunov-type theorem of Akemann and Weaver.

Typo in Appendix corrected. To appear in Advances in Mathematics