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 ξ1,…,ξn with finite support, e.g. {±1} or {0,1}-valued random variables, or some combination thereof. Let u1,…,un∈m and σ2=‖∑i=1nVar[ξi](uiui⁎)2‖. Then there exists a choice of outcomes ε1,…,εn in the support of ξ1,…,ξn s.t. ‖∑i=1nE[ξi]uiui⁎−∑i=1nεiuiui⁎‖≤4σ. A simple consequence of our result is an improvement of a Lyapunov-type theorem of Akemann and Weaver. © 2020 Elsevier.