arXiv preprint ·
Free-Probabilistic State Evolution and Random Matrix Discrepancy
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Probability
Short-maturity skew stickiness ratio under local volatility
Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms
Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions
Exact calibration of structural models via time-change
Get the few papers worth your time in Probability every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.