PaperlayerView exact revision on arXiv

Source-linked AI summary

Free-Probabilistic State Evolution and Random Matrix Discrepancy

August Y. Chen, Ahmed El Alaoui

arXiv:2609.11836v1math.PRcs.DS

TL;DR

The paper asks whether a binary signing can reduce the operator norm in random matrix discrepancy. It develops AMP with state evolution in terms of a correlated Gaussian-semicircular process, then applies the iteration to the discrepancy problem. The resulting algorithm provides an explicit operator-norm expression as a function of the aspect ratio.

  • Problem

    Random matrix discrepancy asks whether a binary vector can make A(x) have operator norm strictly below 2 in the large-dimension limit.

    Source: §1 · p. 2

  • Method

    The paper applies AMP to a random matrix operator and its adjoint, and characterizes fixed-time behavior through state evolution with a correlated Gaussian-semicircular limit.

    Source: §1 · p. 3

  • Results

    The algorithmic solution gives an explicit operator-norm expression as a function of the aspect ratio.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The state evolution result tracks matrix spectral information through strong operator convergence, beyond empirical convergence of entries.

    Source: §1 · p. 3

    The iteration’s linear matrix-message construction constrains its matrix output to have a semicircular strong limit.

    Source: §3.4 · p. 16

Abstract

from arXiv · show

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 \alpha$ 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\sigma(\alpha)$, for an explicit expression of the standard deviation $\sigma(\alpha)<1$ for all $0<\alpha<\alpha_* \simeq 5.74$. This resolves the algorithmic question of Kunisky-Zhang (2023) and Maillard (2025) in this interval.

1 Introduction

The paper studies AMP iterations applied to a random symmetric-matrix operator and seeks an exact high-dimensional description of their behavior. It uses this framework to address random matrix discrepancy, where a binary signing should reduce the operator norm.

1 Introduction

  • The random matrix discrepancy problem asks whether a binary signing can make the operator norm of A(x) strictly smaller than 2 in the large-dimension limit.For an independently chosen unit vector x/√n, the norm is 2 + o_d(1) by Wigner’s semicircle law.Source: §1 · p. 2
  • The proposed algorithmic solution gives an explicit operator-norm expression as a function of the aspect ratio.The introduction identifies this as the application to the discrepancy question.Source: §1 · p. 2
  • The paper applies an Approximate Message Passing iteration to a random matrix-valued linear operator and its adjoint.The matrices are independent, symmetric, and have independent Gaussian upper-triangular entries.Source: §1 · p. 2
  • The goal is an exact asymptotic description of all vector and matrix iterates through each fixed time in the high-dimensional limit.The result takes the form of state evolution, with empirical convergence for vector-side entries and strong operator convergence for matrix-side iterates to a correlated Gaussian-semicircular process.Source: §1 · p. 3

2 Limiting state evolution

For fixed iteration time, the state evolution theorem describes vector-side empirical limits and matrix-side strong operator limits. Its limiting process is a correlated Gaussian-semicircular process, so the matrix limit retains spectral information.

2 Limiting state evolution

  • The theorem assumes a convergent initialization, a positive finite aspect-ratio limit, and regularity and structural conditions on the iteration’s coefficients and nonlinearities.The initialization’s empirical measures converge to Law(U0) in every finite p-Wasserstein distance.Source: §2 · p. 3
  • The limiting process consists of jointly Gaussian vector variables and a semicircular family whose covariances are defined recursively.The covariance relation includes τ(SrSs) = E[GrGs], with Gt = gt(U0, ..., Ut).Source: §2 · p. 4
  • For fixed T, the AMP iterates converge empirically on the vector side and strongly in noncommutative distribution on the matrix side under the theorem’s stated assumptions.The vector-side limit includes the terminal readout, while the matrix-side limit is (S0, ..., ST, W0, ..., WT).Source: §2 · p. 5
  • Strong convergence tracks operator norms as well as normalized traces of polynomials, ensuring that the full limiting spectrum, including outliers, is accounted for.This extends beyond empirical convergence of matrix entries, which does not preserve spectral information.Source: §2 · p. 5
  • An operator-norm stability estimate lets the matrix-discrepancy application round the final AMP output by taking its entrywise sign without worsening the norm guarantee.The terminal readout is included in the state evolution statement.Source: §2 · pp. 4–5
  • The theorem does not include joint strong convergence for A applied to the terminal readout, although the paper notes that such an extension is possible.The authors say the stronger result is not needed for their purposes.Source: §2 · p. 5

3 Application to random matrix discrepancy

The section applies incremental AMP to random matrix discrepancy, constructing an efficient sign-vector algorithm with a nontrivial operator-norm guarantee for α < 5.74216 using an incremental Gaussian-semicircular process, a diffusion-guided martingale, and sign rounding. It analyzes the rounding procedure and calls to A and A*, then discusses the method’s limits, extensions, and open questions, including the scope of its semicircular strong limits.

3 Application to random matrix discrepancy

  • When 2n/d² → α ∈ (0, ∞), for every ε > 0, an efficient algorithm linearly queries A and A* and outputs a sign vector; its calls are bounded by N(α, ε), independent of d.Source: §3 · p. 6

3.1 Incremental AMP

  • The incremental AMP construction has independent Gaussian increments and free semicircular increments, corresponding to discretized Brownian and time-changed free Brownian processes.The paper presents the algorithm as an unconditional nontrivial bound, without attempting to attain the minimum possible operator norm.Source: §3.1 · pp. 7, 9, §3 · p. 7

3.2 A diffusion approach

  • The diffusion approach steers the AMP martingale toward signs by approximating the conditional expected sign of a terminal Brownian motion.It uses a continuous-time process that is discretized at intervals δ, with δ then taken to zero.Source: §3.2 · p. 10

3.3 Rounding

  • The rounding step takes signs of the AMP endpoint to form a binary vector, and the rounding analysis establishes the resulting discrepancy bound.The endpoint sign agrees almost surely with the sign of the coupled Brownian motion at time q.Source: §3.3 · pp. 14–15
  • The iteration through time ℓ−1 uses 2ℓ calls to A and A*, with ℓ depending on ε and α.This is the stated query count for the rounding result.Source: §3.3 · p. 16

3.4 Discussion

  • The diffusion approach solves a slightly modified perceptron problem, requiring x ∈ {−1, +1}ⁿ; thresholds, solution-space structure, and algorithmic tractability are understood to an advanced degree [APZ19] [GKPX22] [HSS26].Source: §3.4 · p. 16
  • Linear-combination matrix messages yield semicircular strong limits and suffice for operator norm below 2; spectral nonlinearities could instead yield free martingales with non-semicircular spectra.The proposed spectral maps include self-adjoint polynomials and incremental maps; their analysis would require free stochastic calculus.Source: §3.4 · pp. 16–17
  • Assumption 2.5 is a technical condition ensuring finite-size empirical Gram-matrix invertibility; small additive Gaussian noise with variance tending to zero offers an alternative.The proposed alternative relies on a stability argument as the noise variance is taken to zero.Source: §3.4 · p. 17
  • Conditioned on operator norm at most 2σ for σ < 1, a typical uniform binary point has a non-semicircular spectrum with explicit density, unlike the algorithm’s semicircular, highly atypical outputs [Mai25].The discussion asks whether algorithms can produce a point with a typical spectrum.Source: §3.4 · p. 17
  • The discussion leaves open the asymptotic minimum of ||A(x)||op and the smallest operator norm achievable by Lipschitz algorithms, noting the latter may be easier to determine [HSS26].The minimum is posed for binary x as 2n/d^2 tends to α.Source: §3.4 · p. 17

4 Adaptive Gaussian conditioning

The section develops a Gaussian decomposition conditional on adaptive linear observations, a main input to the state-evolution proof. Alternating observations of A and A* expose successive directions while preserving an independent Gaussian law on the unrevealed part.

4 Adaptive Gaussian conditioning

  • A conditional Gaussian decomposition after adaptive linear observations is a main input to the state-evolution proof.The observations form an alternating scheme.Source: §4 · pp. 17–18
  • A is a centered isotropic Gaussian operator on the Hilbert–Schmidt operator space, up to scalar variance 2/d^2.Source: §4 · p. 19
  • Conditioning on an action of an isotropic Gaussian operator leaves its restriction to the orthogonal complement independent and isotropic.The same conditioning fact applies to adjoint observations in the range direction.Source: §4 · p. 19
  • The alternating induction reveals domain and range directions in turn, with the unrevealed operator block represented by an independent copy.Source: §4 · pp. 19–21
  • Conditionally on h, an independent copy maps h to a scaled standard GOE matrix; conditionally on k, its adjoint action has independent centered Gaussian coordinates.The passage gives the coordinate variance as α_d‖k‖².Source: §4 · p. 22

5 Gram matrix invertibility

The section establishes almost-sure invertibility of the empirical and limiting Gram matrices used in the conditioning proof. It also proves full rank of the message histories by induction under the stated assumptions and dimension bounds.

5 Gram matrix invertibility

  • Almost surely, both message histories have rank t + 1 for every 0 ≤ t ≤ T when n and dim K_d are at least T + 1.Source: §5 · p. 23
  • Full rank follows inductively because each new message has a nondegenerate conditional Gaussian component outside the span of its predecessors.The conditional-density argument uses invertible coefficients and nonzero diagonal terms.Source: §5 · pp. 23–24

6 Proof of state evolution

The section proves state evolution by induction, tracking matrix-array strong limits and empirical coordinate limits through successive matrix and vector updates. It uses Onsager cancellations to obtain fresh GOE and Gaussian innovations, then closes the vector-update induction to complete Theorem 6.1.

6 Proof of state evolution

  • Under Assumptions 2.1–2.5 and for fixed T, Theorem 6.1 establishes strong convergence of the matrix array to a limiting process whose covariances are given by (2.4)–(2.5).The terminal step and stability of A(bm − m) are proved separately in Section 7.Source: §6 · pp. 24–25

Then we have the joint strong convergence

6.1 The induction argument

  • The proof inducts on time using Bolthausen’s conditioning argument, tracking empirical coordinate convergence and strong convergence of the matrix array.Source: §6.1 · p. 25

6.2 The matrix update

  • The matrix update’s Onsager subtraction cancels conditional-mean terms, yielding a fresh GOE innovation and joint strong convergence to the semicircular matrix process.The limiting semicircular family has covariance τ(S_t S_r) = E[G_t G_r].Source: §6.2 · p. 29

6.3 The vector update

  • The vector update’s Onsager cancellation yields a fresh Gaussian innovation and empirical convergence of the enlarged coordinate array.The error terms are negligible under the stated moment and bounded-normalized-norm controls.Source: §6.3 · pp. 30–31
  • The vector update is G_{t+1}=g_{t+1}(U_0, ..., U_{t+1}); Lemma 6.4 closes the induction H_{t+1}, completing Theorem 6.1.Source: §6.3 · p. 31

7 The terminal query

Section 7 controls a terminal query and extends state evolution by one vector-to-matrix half-step, yielding a joint semicircular limit for the added output. The proof of Theorem 2.9 combines this extension with stability control for the terminal message.

7 The terminal query

  • Terminal-query stability applies to vectors measurable from the observation history, which is crucial because these vectors arise from at most 2T linear measurements of A and A*.For such z, the stated bound is ∥Az∥op ≤ Cd,T ∥z∥n.Source: §7 · p. 33
  • The extra half-step converges jointly with the earlier iterates to a semicircular variable whose covariances are specified by the query and prior process.The limit includes the earlier matrix iterates and messages as well as the added output.Source: §7 · p. 34

7.1 Proof of Theorem 2.9

  • The proof adjoins bounded measurable functions to empirical convergence when their discontinuity sets have zero probability.It uses this step to adjoin h(x_i) to the empirical convergence.Source: §7.1 · p. 34
  • The right-hand side tends to 0 as a → ∞ by (7.5); Lemma 7.2 therefore yields a conclusion, with the assertion made for every η > 0, in this argument.Source: §7.1 · p. 34
Loading 2609.11836v1…