自由概率状态演化与随机矩阵差异
Free-Probabilistic State Evolution and Random Matrix Discrepancy
August Y. Chen, Ahmed El Alaoui
AI 速读 基于摘要
作者为作用于独立高斯随机矩阵线性组合的近似消息传递迭代建立了自由概率意义下的状态演化,并将其用于构造算子范数更小的随机矩阵差异二元向量。
math.PR · cs.DS
查看原文摘要
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_iA_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\to \infty, 2n/d^2 \to α$ 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 a standard deviation $σ(α)<1$ for all $α>0$, and $σ(α) = O(1/\sqrt{α\log α})$ for large $α$. This resolves the algorithmic question of Kunisky-Zhang (2023) and Maillard (2025).