Matrix signs control precision limits on operator sizes
Stable and Online Algorithms for Random Matrix Discrepancy
Data Structures and AlgorithmsComputational ComplexityDiscrete Mathematics
Summary
The paper looks at how to assign positive or negative signs to a collection of large random matrices so that their combined size stays small in a specific technical sense. The authors find precise limits on how many matrices you need compared to their size, depending on how closely you want to control the combined size. They also design efficient procedures that work both when you have all the matrices in advance and when you must choose signs one by one as matrices arrive. Their results show how difficult it is to do this compared to just checking if a solution exists.
What this means in practice
- •For quantitative finance teams: Select portfolio positions with bounded risk by controlling signs of correlated random factors in online trading models.
- •For signal processing engineers: Design stable sign patterns to limit operator norm growth when combining random measurement matrices in high-dimensional systems.
A theory result. No direct application yet.
Authors
Eren C. Kızıldağ, Shuangping Li
Abstract
We study the average-case matrix discrepancy problem: given independent normalized $d\times d$ Gaussian orthogonal ensemble matrices $A_1,\dots,A_N$ and a fixed margin $κ>0$, find signs $σ_1,\dots,σ_N\in\{-1,1\}$ such that the operator norm of $\sum_{i=1}^N σ_i A_i$ is at most $κ\sqrt{N}$. Focusing on the proportional regime $N/d^2\to τ\in(0,\infty)$ as $d\to\infty$ followed by the small-margin limit $κ\downarrow 0$, we characterize the density required by stable offline algorithms and by online algorithms. In the offline setting, we construct a polynomial-time \emph{recenter-and-round} algorithm that is noise-stable and succeeds whenever $τ=Ω(\frac{1}{κ^2\log(1/κ)})$, along with a matching lower bound for all stable algorithms. In the online setting where each sign must be chosen irrevocably upon observing the corresponding matrix, we determine the exact limiting performance of the \emph{Frobenius-greedy} algorithm, establishing that it succeeds when $τ>τ_{\rm FG}(κ)\sim \fracπ{4κ^2}$, as well as a matching lower bound for all online algorithms by conditioning on a revealed prefix. At the core of our algorithms lies rotational symmetry, which enables us to transfer Frobenius norm control into operator norm guarantees. Together, our results identify the algorithmic phase transition points for random matrix discrepancy: $Θ(\frac{1}{κ^2\log(1/κ)})$ for stable offline algorithms and $Θ(\frac{1}{κ^2})$ for online algorithms. Both thresholds lie far above the satisfiability scale $Θ(\log(1/κ))$, as shown by Maillard~\cite{maillard2025}.