Free-Probabilistic State Evolution and Random Matrix Discrepancy
Abstract
Let A1,…,An be independent d × d real symmetric Gaussian random matrices, and consider the linear operator A(x) = n−1/2∑i=1n xi Ai, x∈ ℝ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→ ∞, 2n/d2 → α 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 ∈ {−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<α<α* ≃ 5.74. This resolves the algorithmic question of Kunisky-Zhang (2023) and Maillard (2025) in this interval.
Related
- Stable and Online Algorithms for Random Matrix Discrepancy
- Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer
- A Smoothed Discrepancy Principle for Random Feature Methods and Neural Networks
- A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture
- Discrepancy for Random Linear Codes
BibTeX
@misc{chen2026freeprobabilistic,
title = {{Free-Probabilistic State Evolution and Random Matrix Discrepancy}},
author = {August Y. Chen and Ahmed El Alaoui},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11836},
eprint = {2609.11836},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11836},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Free-Probabilistic State Evolution and Random Matrix Discrepancy
AU - August Y. Chen
AU - Ahmed El Alaoui
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11836
UR - https://arxiv.org/abs/2609.11836
AB - Let A_1,…,A_n be independent d × d real symmetric Gaussian random matrices, and consider the linear operator A(x) = n^−1/2∑_i=1^n x_i A_i, x∈ ℝ^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→ ∞, 2n/d^2 → α 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 ∈ {−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<α<α_* ≃ 5.74. This resolves the algorithmic question of Kunisky-Zhang (2023) and Maillard (2025) in this interval.
ER -