Metraipolis › archive › dc_c331fcbb1a01

A Walk From Free Probability to Matrix Discrepancy I: Matrix Spencer — arXiv:2609.18914

Source

arXiv (en)

Original

https://arxiv.org/abs/2609.18914

License (as archived)

CC0-1.0

Archived

2026-10-15T17:09:22.683Z

SHA-256 of the archived text

a69eee03298f0d96b2228f4674fe6c3f5bade0ea889942c7d99d868212365c0e

Stable URL of this page

https://metraipolis.com/documento/dc_c331fcbb1a01

How to cite

A Walk From Free Probability to Matrix Discrepancy I: Matrix Spencer — arXiv:2609.18914 — arXiv (en), https://arxiv.org/abs/2609.18914 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c331fcbb1a01 (Metraipolis archive dc_c331fcbb1a01, sha256 a69eee03298f0d96b2228f4674fe6c3f5bade0ea889942c7d99d868212365c0e)

@misc{dcc331fcbb1a01,
  title = {A Walk From Free Probability to Matrix Discrepancy I: Matrix Spencer — arXiv:2609.18914},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.18914},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c331fcbb1a01; sha256 a69eee03298f0d96b2228f4674fe6c3f5bade0ea889942c7d99d868212365c0e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18914. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Matrix Spencer conjecture asks whether any $n$ real symmetric matrices A_1,...,A_n \in \mathbb{R}^{m \times m} of operator norm at most one admit a signing $x\in\{-1,1\}^n$ such that the operator norm of the signed sum is at most O(\sqrt{n \log(2m/n)}) We give a randomized algorithm establishing this bound with polynomial runtime in the real-arithmetic model. We first prove the $O(\sqrt n)$ bound for $m\le n$, resolving the square case, and then obtain the rectangular bound by changing the regularizer. As in earlier algorithmic discrepancy methods \cite{lovettmeka2012,bansalLaddhaVempala2022,pesentivladu2026}, we run a covariance-controlled random walk from the origin of the hypercube, rounding coordinates near its faces and keeping them fixed. Our potential measures a soft spectral edge of the evolving discrepancy matrix perturbed by an operator-valued free semicircular element. Inspired by the free interpolation approach of \cite{bbvh2023}, we combine Lehner's variational formula for the free edge \cite{lehner1999} with spectral Tsallis regularization \cite{allenZhuLiaoOrecchia2015,pesentivladu2026}. This puts the discrepancy and remaining covariance in a single smooth optimization problem. The potential has a finite-dimensional semidefinite formulation. Stability of its optimizer, governed by equations related to the matrix Dyson equation \cite{erdos2019}, lets us find a large subspace in which to move while controlling discrepancy. The square case uses the Tsallis--$1/2$ regularizer; the rectangular case uses a suitable generalized Tsallis power regularizer. Our companion paper \cite{kathuria2026ks} applies these ideas to give an algorithmic proof of Weaver's discrepancy theorem, whose existence proof by [MSS15] resolved the Kadison--Singer conjecture \cite{mss2015}.Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.18914 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T16:17:15.271Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).