Matrix discrepancy bounds achieved with new randomized algorithm
A Walk From Free Probability to Matrix Discrepancy I: Matrix Spencer
Data Structures and Algorithms
Summary
This paper deals with a math problem about combining several square grids of numbers so their combined effect stays within certain limits. The authors developed a fast randomized method to pick signs for each matrix that ensures the combined size doesn't get too big, even for very large matrices. They solved the hardest case when the matrices are square and then extended their approach to rectangular matrices. Their work builds on ideas from randomness and optimization to control how these combined matrices behave.
What this means in practice
- •For optimization engineers: Use the new algorithm for balancing large sets of symmetric matrices with operator norm constraints to improve numerical stability in optimization routines.
- •For signal processing teams: Implement matrix signing techniques to enhance error controls when combining multiple data covariance matrices in signal analysis algorithms.
A theory result. No direct application yet.
Authors
Tarun Kathuria
Abstract
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.