Algorithm finds near-optimal signs for matrix discrepancy problems
A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture
Data Structures and Algorithms
Summary
The paper addresses an important mathematical problem about assigning plus or minus signs to numbers to keep certain matrix properties balanced. Previous work showed such assignments always exist but did not provide a practical way to find them quickly. The authors develop a step-by-step algorithm that efficiently picks signs while controlling a measure of error called discrepancy. Their method uses advanced mathematical tools from free probability and optimization theory to guide this sign selection process. This resolves an open question about doing this efficiently in general.
What this means in practice
- •For linear algebra software developers: Implement algorithms that find near-optimal signings to reduce matrix discrepancy in large-scale numerical computations.
- •For quantum computing engineers: Use efficient sign assignment methods to design matrices with controlled spectral properties relevant for quantum information tasks.
A theory result. No direct application yet.
Authors
Tarun Kathuria
Abstract
\cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison--Singer conjecture . Finding such signs efficiently for general inputs remained an open algorithmic question. In the real-arithmetic model, we give a deterministic algorithm running in polynomial time with discrepancy at most $35\sqrt\varepsilon$. The algorithm walks from the origin of the hypercube to a vertex, fixing coordinates as they hit a face. Its potential measures a soft spectral edge of the discrepancy matrix perturbed by an operator-valued free semicircular element. The perturbation's covariance vanishes as the coefficients reach their endpoints. Inspired by the free interpolation approach of Bandeira, Boedihardjo, and van Handel \cite{bbvh2023}, we combine Lehner's variational formula \cite{lehner1999} with spectral Tsallis--$1/2$ regularization used in \cite{allenZhuLiaoOrecchia2015} and \cite{pesentivladu2026}. The resulting potential has a finite-dimensional SDP formulation, allowing the discrepancy and remaining covariance to be analyzed together. We analyze the optimizer's stability through the linearized Karush--Kuhn--Tucker (KKT) system of a regularized min--max problem, whose stationarity equations are related to the matrix Dyson equation \cite{erdos2019}. This gives the movement rule: either a coordinate can move toward its nearer endpoint at small spectral cost, or a low-curvature direction orthogonal to the current coefficient vector allows further progress. Choosing the better sign of this direction controls discrepancy while increasing the squared distance from the origin. Upcoming work \cite{kathuria2026higherRank} will address higher-rank Kadison-Singer and spectrally thin trees. Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.