Four Deviations Suffice for Rank 1 Matrices

Understand

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, \ldots, \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 = \left\| \sum_{i=1}^n \text{Var}[ \xi_i ] (u_i u_i^{*})^2 \right\|.