2021/11/04 by Dadush, Daniel, Jiang, Haotian, Reis, Victor
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2111.03171
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) Bn_∞, and construct such a cover via mirror descent. As applications of our framework, we show: \bullet Matrix Spencer for Low-Rank Matrices. If the matrices satisfy ‖Ai‖op ≤ 1 and rank(Ai) ≤ r, we can efficiently find a coloring x ∈ \± 1\n with discrepancy ‖∑i=1n xi Ai ‖op \lesssim √(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 r m ≤ n. \bullet Matrix Spencer for Block Diagonal Matrices. For block diagonal matrices with ‖Ai‖op ≤ 1 and block size h, we can efficiently find a coloring x ∈ \± 1\n with ‖∑i=1n xi Ai ‖op \lesssim √(n log (hm/n)). 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. \bullet Matrix Discrepancy for Schatten Norms. We generalize our discrepancy bound for matrix Spencer to Schatten norms 2 ≤ p ≤ q. Given ‖Ai‖Sp ≤ 1 and rank(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 \lesssim √(n min(p, log(rk))) ⋅ k1/p-1/q, where k := min(1,m/n).