A new framework for matrix discrepancy: partial coloring bounds via mirror descent

Motivated by the Matrix Spencer conjecture, we study the problem of finding signed sums of matrices with a small matrix norm. A well-known strategy to obtain these signs is to prove, given matrices A 1 , . . . , A n ∈ R m×m , a Gaussian measure lower bound of 2 -O(n) for a scaling of the discrepancy body x ∈ R n : n i=1 x i A i ≤ 1. We show this is equivalent to covering its polar with 2 O(n) translates of the cube 1 n B n ∞ , and construct such a cover via mirror descent. As applications of our framework, we show: Matrix Spencer for Low-Rank Matrices. If the matrices satisfy A i op ≤ 1 and rank(A i ) ≤ r, we can efficiently find a coloring x ∈ ±1 n with discrepancy n i=1 x i A i op n log(min(rm/n, r)). This improves upon the naive O( √ n log r) bound for random coloring and proves the matrix Spencer conjecture when rm ≤ n.

For block diagonal matrices with A i op ≤ 1 and block size h, we can efficiently find a coloring x ∈ ±1 n with n i=1 x i A i op n log(hm/n). This bound was previously shown in [Levy, Ramadas and Rothvoss, IPCO 2017] under the assumption h ≤ √ n, which we remove. Using our proof, we reduce the matrix Spencer conjecture to the existence of a O(log(m/n)) quantum relative entropy net on the spectraplex.