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: