A new framework for matrix discrepancy: partial coloring bounds via mirror descent
A new framework for matrix discrepancy: partial coloring bounds via mirror descent
复制标题
矩阵差异的新框架：通过镜像下降的部分着色边界
DOI：
10.1145/3519935.3519967
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Victor Reis
中科院分区：
文献类型：
--
作者：
D. Dadush;Haotian Jiang;Victor Reis
受矩阵Spencer猜想的启发，本文研究了矩阵范数较小的矩阵的符号和问题。获得这些符号的一个众所周知的策略是证明，给定矩阵A1，...，An ∈ m × m，对于差异体{x ∈ m × n：||∑ i = 1n xi Ai|| ≤ 1}。我们证明了这等价于用立方1/n B ∞ n的2O（n）个平移覆盖它的极坐标，并通过镜像下降构造了这样一个覆盖.作为我们框架的应用，我们展示了：低秩矩阵的矩阵Spencer。如果矩阵满足||AI|| ≤ 1且（Ai）≤ r，我们可以有效地找到一个具有偏差的着色x ∈ {± 1} n|| ∑ i = 1n xi Ai|| √ n log（min（rm/n，r））。这改进了随机着色的朴素O（n-logr）界，并证明了当rm ≤ n时矩阵Spencer猜想.块对角矩阵的矩阵Spencer。对于块对角矩阵，||AI|| ≤ 1和块大小h，我们可以有效地找到一个着色x ∈ {± 1} n，||∑ i = 1n xi Ai|| n log（hm/n）。这个界限以前在[Levy，Ramadas和Rothvoss，IPCO 2017]中在假设h ≤ n的情况下显示，我们删除了它。利用我们的证明，我们将矩阵Spencer猜想归结为在谱丛上存在一个O（log（m/n））的量子相对熵网. Schatten范数的矩阵离散性我们将矩阵Spencer的偏差界推广到Schatten范数2 ≤ p ≤ q。给定||AI|| Sp ≤ 1且（Ai）≤ r，我们可以有效地找到一个部分染色x ∈ [-1，1] n，其中|{i：|习|= 1}| ≥ n/2且||∑ i = 1n xi Ai|| Sq n min（p，log（rk））·k1/p − 1/q，其中k：= min（1，m/n）。当m = θ（n）时，我们的部分着色界是紧的.当m = n时，我们还给出了秩为1的矩阵Spencer的Ω（m，n）的紧下界，当S2 → S ∞时，我们给出了Ω（m，n）的紧下界，排除了Komlós猜想的矩阵形式.
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.
影响因子：
3.1
作者：
Bandeira, Afonso S.;Boedihardjo, March T.;van Handel, Ramon
通讯作者：
van Handel, Ramon
DOI：
10.1145/3519935.3519954
发表时间：
2022
期刊：
ACM Symposium on Theory of Computing
影响因子：
--
作者：
Hopkins, Samuel B.;Raghavendra, Prasad;Shetty, Abhishek
通讯作者：
Shetty, Abhishek