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 A1, …, An ∈ ℝm × m, a Gaussian measure lower bound of 2−O(n) for a scaling of the discrepancy body {x ∈ ℝn: || ∑i=1n xi Ai|| ≤ 1}. We show this is equivalent to covering its polar with 2O(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 ||Ai||≤ 1 and (Ai) ≤ r, we can efficiently find a coloring x ∈ {± 1}n with discrepancy ||∑i=1n xi Ai ||≲ √n log(min(rm/n, r)). This improves upon the naive O(√n logr) bound for random coloring and proves the matrix Spencer conjecture when r m ≤ n. Matrix Spencer for Block Diagonal Matrices. For block diagonal matrices with ||Ai||≤ 1 and block size h, we can efficiently find a coloring x ∈ {± 1}n with ||∑i=1n xi Ai ||≲ √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. Matrix Discrepancy for Schatten Norms. We generalize our discrepancy bound for matrix Spencer to Schatten norms 2 ≤ p ≤ q. Given ||Ai||Sp ≤ 1 and (Ai) ≤ r, we can efficiently find a partial coloring x ∈ [−1,1]n with |{i : |xi| = 1}| ≥ n/2 and ||∑i=1n xi Ai||Sq ≲ √n min(p, log(rk)) · k1/p−1/q, where k := min(1,m/n). Our partial coloring bound is tight when m = Θ(√n). We also provide tight lower bounds of Ω(√n) for rank-1 matrix Spencer when m = n, and Ω(√min(m,n)) for S2 → S∞ discrepancy, precluding a matrix version of the Komlós conjecture.

• View at Publisher

Free Full Text ( Final Version , 293kb )