English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Motivated by the Matrix Spencer conjecture, we study the problem of findingsigned sums of matrices with a small matrix norm. A well-known strategy toobtain these signs is to prove, given matrices $A_1, \dots, A_n \in\mathbb{R}^{m \times m}$, a Gaussian measure lower bound of $2^{-O(n)}$ for ascaling of the discrepancy body $\{x \in \mathbb{R}^n: \| \sum_{i=1}^n x_iA_i\| \leq 1\}$. We show this is equivalent to covering its polar with$2^{O(n)}$ translates of the cube $\frac{1}{n} B^n_\infty$, and construct sucha cover via mirror descent. As applications of our framework, we show:  $\bullet$ Matrix Spencer for Low-Rank Matrices. If the matrices satisfy$\|A_i\|_{\mathrm{op}} \leq 1$ and $\mathrm{rank}(A_i) \leq r$, we canefficiently find a coloring $x \in \{\pm 1\}^n$ with discrepancy$\|\sum_{i=1}^n x_i A_i \|_{\mathrm{op}} \lesssim \sqrt{n \log (\min(rm/n,r))}$. This improves upon the naive $O(\sqrt{n \log r})$ bound for randomcoloring and proves the matrix Spencer conjecture when $r m \leq n$.  $\bullet$ Matrix Spencer for Block Diagonal Matrices. For block diagonalmatrices with $\|A_i\|_{\mathrm{op}} \leq 1$ and block size $h$, we canefficiently find a coloring $x \in \{\pm 1\}^n$ with $\|\sum_{i=1}^n x_i A_i\|_{\mathrm{op}} \lesssim \sqrt{n \log (hm/n)}$. Using our proof, we reduce thematrix Spencer conjecture to the existence of a $O(\log(m/n))$ quantum relativeentropy net on the spectraplex.  $\bullet$ Matrix Discrepancy for Schatten Norms. We generalize ourdiscrepancy bound for matrix Spencer to Schatten norms $2 \le p \leq q$. Given$\|A_i\|_{S_p} \leq 1$ and $\mathrm{rank}(A_i) \leq r$, we can efficiently finda partial coloring $x \in [-1,1]^n$ with $|\{i : |x_i| = 1\}| \ge n/2$ and$\|\sum_{i=1}^n x_i A_i\|_{S_q} \lesssim \sqrt{n \min(p, \log(rk))} \cdotk^{1/p-1/q}$, where $k := \min(1,m/n)$.

A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent