Algorithm finds low norm binary vectors in large random matrix problems
Free-Probabilistic State Evolution and Random Matrix Discrepancy
Data Structures and Algorithms
Summary
Some problems involve choosing signs for numbers to make a related large matrix have small effects. The paper studies an iterative method that looks like a message passing process and analyzes its behavior as matrices get very large. This analysis uses advanced math from free probability theory to predict how the method works. The method then finds binary sign choices that keep the matrix operation small, solving a previous open question in a certain range of parameters.
What this means in practice
- •For optimization engineers: Use the iterative algorithm to find binary solutions that control large matrix operator norms in optimization tasks.
- •For signal processing teams: Apply the method to design signals or codes with bounded operator norms to improve system robustness.
A theory result. No direct application yet.
Authors
August Y. Chen, Ahmed El Alaoui
Abstract
Let $A_1,\ldots,A_n$ be independent $d \times d$ real symmetric Gaussian random matrices, and consider the linear operator $A(x) = n^{-1/2}\sum_{i=1}^n x_i A_i$, $x\in \mathbb{R}^n$. We construct an iterative algorithm in the Approximate Message Passing family which iterates over $A$ and its adjoint $A^*$, and establish a state evolution result which characterizes its behavior in the limit $d\rightarrow \infty, 2n/d^2 \rightarrow α$ in terms of a correlated Gaussian-semicircular process in a free probability space, in the sense of strong convergence of operators. We then apply this iteration to the random matrix discrepancy problem which asks for a binary vector $x \in \{-1,+1\}^n$ such that $A(x)$ has a small operator norm. Our algorithm achieves an operator norm $2σ(α)$, for an explicit expression of the standard deviation $σ(α)<1$ for all $0<α<α_* \simeq 5.74$. This resolves the algorithmic question of Kunisky-Zhang (2023) and Maillard (2025) in this interval.