PaperlayerView exact revision on arXiv

Source-linked AI summary

Universality of approximate message passing under a fourth-moment tail condition

Ripunjay Dwivedi, Taejoon Kim

arXiv:2610.28971v1cs.ITmath.ITmath.PRmath.STstat.TH

TL;DR

AMP state evolution is established for independent, non-Gaussian rectangular matrices under fourth-power tail conditions, despite matrix reuse complicating the full recursion. The proof transfers the Gaussian state evolution limit, and the paper also characterizes when complementary projected components are independent.

  • Problem

    Because later AMP updates reuse the matrix and depend on earlier iterates, a central limit theorem for the first multiplication does not establish state evolution for the full recursion.

    Source: §1 · p. 2

  • Method

    The universality argument transfers the Gaussian state evolution limit to non-Gaussian ensembles, with the theorem covering independent entries under fourth-power uniform integrability.

    Source: §1 · p. 2, §2.4 · p. 5

  • Results

    At every fixed iteration, empirical averages of order-two pseudo-Lipschitz functions converge in probability to their Gaussian state evolution limits.

    Source: §1 · p. 2, §2.5 · p. 6

  • Takeaways & Limitations

    Independence of the two orthogonal projections for every rank-one constraint pair characterizes Gaussian entries under the stated independent-entry, centering, and variance assumptions.

    Source: §1 · p. 2, §2.5 · p. 7

    The result is an averaged asymptotic statement and gives no entrywise bounds under weaker moment assumptions.

    Source: §8.3 · p. 29

Abstract

from arXiv · show

We prove state evolution for approximate message passing (AMP) with rectangular random matrices whose entries are independent, centered, and variance-normalized. The row and column dimensions grow with a ratio that converges to a positive finite limit. The entry laws may differ across coordinates and dimensions, and we assume uniform integrability of the fourth powers of the rescaled entries. For entries sampled independently from a fixed law, a finite fourth moment suffices, with no requirement for higher moments. The nonlinearities are continuously differentiable and globally Lipschitz, with bounded continuous first state derivatives. The signal and noise have independent and identically distributed coordinates with finite moments of all orders, and are independent of each other and of the matrix. At every fixed number of iterations, empirical averages of pseudo-Lipschitz functions of order two converge in probability to the limits specified by Gaussian state evolution. These averages include empirical second moments and products of trajectory coordinates. The proof combines an aggregate bound on third derivatives with randomized Lindeberg replacement and operator-norm truncation, without matching third moments or invoking a non-Gaussian universality theorem. We also show that independence of complementary projected components for every deterministic rank-one constraint pair characterizes Gaussian entries. This identifies the limitation of extending Gaussian conditioning identities to independent non-Gaussian matrices. Finally, a variance-profile example shows that average variance normalization alone does not ensure the homogeneous state evolution limits.

1 Introduction

The paper establishes AMP state evolution beyond Gaussian matrices under fourth-power tail conditions. It addresses why a first-step central limit theorem is insufficient for the full recursion and explains how its assumptions differ from prior results.

1 Introduction

  • Repeated matrix use makes later AMP updates depend on earlier iterates, so a central limit theorem for the first multiplication does not establish the full recursion.Source: §1 · p. 2
  • For independent, centered, variance-normalized rectangular matrices, order-two pseudo-Lipschitz empirical averages converge in probability to Gaussian state evolution limits at every fixed iteration.The assumptions include jointly C1, globally Lipschitz nonlinearities with bounded continuous first derivatives and the stated side-data conditions; the averages include squared errors and trajectory-coordinate products.Source: §1 · p. 2
  • Earlier universality results use differing matrix and algorithm assumptions, including polynomial iterations or sub-Gaussian matrices for continuously differentiable or Lipschitz nonlinearities.Other cited approaches include tensor networks, tree pairings, dynamical cavity methods, and diagrammatic expansions.Source: §1 · p. 2
  • The result replaces sub-Gaussian or all-moment assumptions with fourth-power uniform integrability, and fixed-law i.i.d. entries require only a finite fourth moment.The paper notes that this condition and the entry-moment condition in do not nest.Source: §1 · p. 2
  • Nguyen and Kim [18] use an affine projection formula to characterize conditional distributions, but that step requires complementary projected components to be independent.The paper proves that this independence for every deterministic rank-one constraint pair holds if and only if the entries are Gaussian, and establishes its result without non-Gaussian conditioning.Source: §1 · p. 2

2 Setup and Main Results

The section sets up two-stage AMP and its Gaussian state-evolution reference, then states convergence results for empirical trajectory statistics and a characterization of when deterministic projection independence holds. The analysis uses fourth-moment conditions and the stated regularity and side-data assumptions.

2.1 Notation

  • PL(2) tests obey a quadratic-growth Lipschitz bound, and the preliminary results include a fourth-moment law of large numbers with almost-sure convergence under bounded fourth central moments.The notation also distinguishes the empirical mean and componentwise application of scalar functions.Source: §2.1 · p. 3, §2.3 · p. 5

2.2 The algorithm and the assumptions

  • The recursion uses independent matrix entries with aspect ratio tending to a positive finite limit, jointly continuously differentiable globally Lipschitz nonlinearities, and independent i.i.d. signal and noise coordinates with all moments finite.The matrix entries are centered and variance-normalized; fourth-power uniform integrability also covers fixed entry laws with finite fourth moment.Source: §2.2 · p. 4

2.3 Preliminaries

  • The section states an even-moment Rosenthal inequality for independent centered variables and a matrix norm bound for independent mean-zero entries.The cited bounds are presented as probabilistic and matrix-analytic tools for later proofs.Source: §2.3 · p. 5

2.4 State evolution

  • AMP alternates matrix multiplications and coordinatewise nonlinearities, with Onsager corrections compensating for leading effects of matrix reuse; its Gaussian limit is described by a deterministic covariance recursion.The state-evolution construction uses centered jointly Gaussian families independent of the signal and noise.Source: §2.4 · pp. 5–6

2.5 Main results

  • At each fixed iteration, empirical mean-square statistics converge in probability to their state-evolution limits, with L1 convergence also stated for bounded tests in the original ensemble and PL(2) tests at fixed matrix cutoff.The paper also gives an almost-sure subsequence result when ensembles share a probability space.Source: §2.5 · pp. 6–7
  • Aggregate variance normalization alone does not imply state evolution, and almost-sure convergence is treated separately from the fixed-iteration convergence results.The section also contrasts the fourth-power condition with the weaker condition sufficient for the first row update.Source: §2.5 · p. 7
  • For every rank-one constraint pair, independence of the two complementary orthogonal projections holds if and only if the independent, centered, variance-1/n entries are i.i.d. N(0, 1/n).The paper notes that every non-Gaussian ensemble under these entry assumptions fails this property for some pair.Source: §2.5 · p. 7

3 Gaussian Matrices and Orthogonal Conditioning

Orthogonal projections separate a Gaussian matrix into constrained and unconstrained components, yielding an exact conditional-law representation. Universal independence of these complementary components is a Gaussian characterization, not a general property of independent-entry matrices.

3.1 Gaussian conditioning via orthogonal projections

  • The projection Π is onto matrices H satisfying P_MH = 0 and HP_Q = 0, while Π⊥(C) is determined by CQ and M∗C.The observations G∗M and GQ determine Π⊥(G), the constrained component used in the Gaussian conditioning formula.Source: §3.1 · pp. 7–8
  • For Gaussian matrices, the projections onto the constrained and unconstrained components are independent, giving a conditional distribution of the form B + Π(G′).The conditioning observations are G∗M and GQ, and G′ is an independent copy of G.Source: §3.1 · p. 8

3.2 Geometric characterization of the Gaussian ensemble

  • Independence of complementary projections for every rank-one constraint pair holds if and only if independent centered entries of variance 1/n are i.i.d. Gaussian.The characterization fails if the condition is restricted to coordinate subspaces, whose projections are independent for any independent-entry ensemble.Source: §3.2 · pp. 8–9
  • Non-Gaussian ensembles can have identical mixed entry moments at every order while having different matrix laws.Neither ensemble satisfies the universal projection-independence property.Source: §3.2 · pp. 8–9
  • For Gaussian iterates, the state-evolution conclusions hold in probability, and bounded pseudo-Lipschitz statistics converge in every finite Lp.The auxiliary iterates with deterministic coefficients satisfy the same conclusions in probability.Source: §3.2 · p. 9

4 Universality of the Trajectory

This section develops an auxiliary AMP recursion with deterministic bounded Onsager coefficients and establishes energy, stability, coordinate-moment, and derivative bounds. It uses randomized Lindeberg replacement to compare trajectories from independent matrix ensembles with matching variances under the stated smoothness and moment conditions.

4 Universality of the Trajectory

  • An auxiliary recursion with uniformly bounded deterministic Onsager coefficient sequences is introduced to decouple matrix randomness from the nonlinear empirical averages defining the true coefficients.The recursion starts from h0 = 0 and m−1 = 0.Source: §4 · p. 9

4.1 Energy and perturbation estimates

  • For identical side data, auxiliary recursions are stable under changes to the matrix, maps, and coefficients, with normalized trajectory discrepancies bounded by a dimension-independent polynomial.The bound holds through any fixed time horizon when the maps satisfy the stated joint Lipschitz and boundedness assumptions and the aspect ratios stay bounded.Source: §4.1 · pp. 10–11

4.2 Coordinate moments by removal of a row or a column

  • Removing a row or column yields coordinate moment bounds for the auxiliary iterates by exploiting independence of the removed entries from the cavity recursion.The cavity moment lemma is stated for fixed p ≥ 1 under the subsection’s sub-Gaussian entry assumption.Source: §4.2 · pp. 11–12

4.3 Entry derivatives and their sources

  • Entry derivatives through order three admit finite source expansions, with propagation operators independent of the differentiated matrix-entry index.For fixed time horizon, the number of expansion terms and the propagation-operator norm bounds depend on the horizon and the matrix norm bound.Source: §4.3 · pp. 12–13

4.4 The aggregate third derivative

  • The aggregate third derivative of an empirical observable is bounded by combining the trajectory derivative estimates across coordinates.For fixed time horizon, the proof bounds the total source contribution by a constant times D^2 K^aT R^3 before dividing by the observable dimension d ≍ D.Source: §4.4 · pp. 15–16
  • The aggregate third-derivative argument sums entrywise contributions to establish the needed derivative bounds for F = p(H).The passage states that the bound for F = p(H) follows after absorbing powers of K.Source: §4.4 · p. 17

4.5 Moving the Taylor base point

  • Changing one matrix entry by y changes trajectory derivatives by bounds proportional to |y| times a polynomial in the entry and trajectory bounds, enabling control of Taylor expansions at a moving base point.Bounded higher derivatives and (S3) make the first derivatives of the nonlinearities globally Lipschitz.Source: §4.5 · pp. 17–19

4.6 Randomized replacement

  • Randomized replacement gives an O(n^-1/2+ε) trajectory comparison for independent centered matrices with identical variances, shared independent side data, bounded deterministic coefficients, and the stated smoothness and tail conditions.The proof bounds the Taylor remainder, base-point difference, and cubic term before integrating over the replacement parameter.Source: §4.6 · pp. 19–20

5 Proof of the Main Theorem

The proof establishes the main theorem through smoothing, observable cutoffs, and matrix truncation, then restores the empirical Onsager coefficients. These steps transfer the Gaussian state-evolution limits to the original trajectory and its pseudo-Lipschitz statistics.

5 Proof of the Main Theorem

  • The proof compares maps at matrix and smoothing cutoffs, takes the dimension limit, and then removes the smoothing, observable, and matrix cutoffs.The final theorem proof applies the Gaussian auxiliary limit, extends it to PL(2), transfers it through truncation, and restores empirical coefficients.Source: §5 · p. 20, §5.4 · p. 23

5.1 Removing the higher-order regularity

  • State-variable mollification supplies smooth approximations with uniformly bounded Lipschitz constants and vanishing approximation error, enabling comparison under C1 regularity.The qualitative comparison transfers convergence from the smoothed observables to the original ones as the smoothing scale tends to zero.Source: §5.1 · pp. 20–21

5.2 Pseudo-Lipschitz observables at fixed cutoff

  • Convergence for bounded smooth observables extends to PL(2) observables, while tight trajectory norms and vanishing normalized trajectory differences transfer their empirical statistics.The resulting PL(2) empirical statistics are bounded in L2 uniformly in dimension.Source: §5.2 · p. 21

5.3 Removing matrix truncation

  • Uniform truncation transfer approximates the original auxiliary trajectory and its pseudo-Lipschitz statistics by those for a truncated matrix as the cutoff grows.The argument uses fourth-power uniform integrability and takes the dimension limit before removing the matrix truncation.Source: §5.3 · p. 22

5.4 Continuous derivative tests and empirical coefficients

  • Restoring empirical Onsager coefficients makes the true and auxiliary trajectories asymptotically close in normalized discrepancy and yields convergence of the empirical coefficients.The proof then obtains L1 convergence for bounded statistics and extends it to unbounded tests at a fixed matrix cutoff.Source: §5.4 · p. 23

6 Aggregate Variance Normalization Is Insufficient

A two-row-group variance profile satisfies aggregate normalization but produces a non-Gaussian mixture at the first update, rather than the homogeneous Gaussian state-evolution limit. Thus aggregate variance normalization alone does not ensure the stated conclusion.

6 Aggregate Variance Normalization Is Insufficient

  • For c1 ≠ c2 with (c1 + c2)/2 = 1, the aggregate-normalized example has a t = 0 empirical limit equal to an equally weighted mixture of Gaussians, not the homogeneous state-evolution limit.The construction takes n even; for some bounded continuous test, including ψ(x) = cos x, the two limits differ.Source: §6 · p. 24
  • The counterexample shows that general variance profiles require profile-dependent formulations rather than the homogeneous state-evolution conclusion.Source: §6 · p. 24
  • Conditioning on the initial side-data vector reduces each row update to a sum of independent centered terms, and bounded test-function averages concentrate around the resulting row expectations.The proof uses conditional variance bounds and a Lyapunov comparison; the limit is uniform over rows with identical variance.Source: §6 · p. 24
  • A cosine test distinguishes the mixture limit from the homogeneous prediction whenever c1 ≠ c2 and σ0^2 > 0.The difference follows from strict convexity of the relevant exponential expression for nonzero θ.Source: §6 · p. 24

7 Almost-Sure Convergence and the Moment Boundary

The section gives conditions for almost-sure convergence and examines where the fourth-power uniform-integrability condition is sufficient, weaker first-update assumptions, and the moment boundary. It also shows that fourth-power uniform integrability is not necessary for Gaussian state-evolution limits in probability.

7.1 Fourth-moment concentration and almost-sure convergence

  • Theorem 7.2 gives almost-sure convergence along summably controlled subsequences, then extends it to finite collections of tests and horizons and, by diagonalization, countable collections.Source: §7.1 · p. 25
  • Under the stated boundedness and approximation conditions, true-trajectory PL(2) statistics inherit almost-sure limits from the approximating sequence.The conditions include vanishing normalized trajectory differences and bounded operator and side-data norms.Source: §7.1 · p. 25

7.2 The moment boundary

  • Under Assumption 2.3 alone, the truncation error tends to zero without a guaranteed polynomial rate in the truncation level; a rate for full state evolution also needs control of other approximation steps.Source: §7.2 · p. 26
  • The first row update b0 is covered under uniform square-integrability, but Proposition 7.3 does not cover the later update h1, which reuses the matrix.Source: §7.2 · pp. 26–27
  • A variance-normalized array with bounded fourth moments can fail fourth-power uniform integrability yet still have Gaussian state-evolution limits in probability.The construction has fourth-moment tail mass bounded below for every fixed truncation level, while the matrix is close in probability to a Gaussian matrix.Source: §7.2 · p. 27

8 Scope

The comparison examples separate the paper’s fourth-power uniform-integrability condition from other moment and model assumptions. The scope discussion also limits the conclusion to averaged convergence and the stated smoothness and independence setting.

8.1 The comparison ensembles

  • The Pareto example has a finite 9/2 moment but an infinite fifth moment, while satisfying Assumption 2.2.It illustrates an entry law allowed by that moment assumption despite lacking moments above order four.Source: §8.1 · p. 27
  • The stretched-exponential example has all moments but is neither sub-Gaussian nor sub-exponential, so it falls outside cited sub-Gaussian hypotheses.Its moment growth is (E|µ|^k)^(1/k) ≍ k^2.Source: §8.1 · p. 27
  • Two entry laws with a shared polynomial tail bound give the same state evolution limit, although their finite-dimensional trajectory laws may differ.The example alternates standardized Pareto and Rademacher entries.Source: §8.1 · p. 28
  • Aggregate variance normalization does not ensure the homogeneous state-evolution conclusion for a nonconstant profile.For the two-valued row profile, the first-row empirical law is a Gaussian scale mixture.Source: §8.1 · p. 28
  • The sparse example meets ’s entry-moment condition but fails the uniform square-integrability condition used here.Its classical dimension-scaled Lindeberg condition holds for bounded initialization weights; applying still requires its other hypotheses.Source: §8.1 · p. 28
  • Soft thresholding is Lipschitz but non-differentiable at its thresholds, so it fails this theorem’s C1 assumption.No non-smooth extension of the empirical-coefficient theorem is asserted.Source: §8.1 · p. 28

8.2 The moment methods in detail

  • The moment conditions of and this theorem do not nest, and applying also requires its side-information, spectral, and nonlinearity assumptions.The examples include one ensemble satisfying each condition while violating the other.Source: §8.2 · pp. 28–29

8.3 Extensions and Outlook

  • The theorem’s conclusion is averaged: it gives no entrywise bounds under weaker moment assumptions.The theorem requires independent entries with equal variances; the variance-profile and sparse examples each violate a stated hypothesis.Source: §8.3 · p. 29

A Proofs for the Preliminaries (Section 2.3)

The preliminary proofs bound moments and tails using independence, then control operator norms through sphere nets and an integrated tail estimate.

A Proofs for the Preliminaries (Section 2.3)

  • The multinomial expansion leaves only terms with multiplicities at least two, yielding a bound of (8p)^(2p) for the moment estimate.The proof bounds products by Q^r and controls the multinomial coefficients and compositions before summing over r.Source: A Proofs for the Preliminaries… · p. 30
  • A fourth-moment bound and Borel–Cantelli give almost-sure convergence for the row sums, including arrays with row-wise independence.The row-sum bound is E(∑_k Y_d,k)^4 ≤ 2C²M₄d².Source: A Proofs for the Preliminaries… · p. 30
  • Sphere nets and a union bound give an operator-norm tail whose integration yields uniformly bounded moments of every fixed positive order.This estimate is used in Lemmas 4.3 and 5.3.Source: Sub-Gaussian operator-norm moments · p. 30

B Perturbations of the Empirical-Coefficient Recursion

The perturbation principle transfers trajectory behavior between nearby matrices when side data and maps match. Its proof propagates normalized trajectory differences through the updates, using continuity of empirical Onsager coefficients.

B Perturbations of the Empirical-Coefficient Recursion

  • If two matrices use identical side data and maps, have tight operator norms and normalized side-data norms, and differ by oP(1) in operator norm, their trajectories have vanishing normalized Euclidean difference at each fixed time.With pathwise convergence and eventual norm boundedness, the trajectory convergence is pathwise.Source: B Perturbations of the… · p. 31
  • The induction propagates discrepancies through the updates using Lipschitz continuity and continuity of the empirical Onsager coefficients.The proof first controls the q discrepancy, then the coefficients, the m and ξ discrepancies, and finally the transpose update for h.Source: B Perturbations of the… · p. 31
  • With globally Lipschitz first derivatives, coefficient differences have a linear bound; under Assumption 2.4, only a qualitative continuity bound is guaranteed.The examples require this qualitative conclusion.Source: B Perturbations of the… · p. 31

B.1 The Gaussian input at degenerate covariances

The proof handles degenerate Gaussian covariances by approximation, avoiding covariance inverses and any uniform lower bound on eigenvalues. A separate truncation observation explains when truncation changes no entries almost surely and what is needed for almost-sure state evolution.

B.1 The Gaussian input at degenerate covariances

  • The induction establishes positive definiteness of enlarged Gram matrices and Gaussian covariance matrices at each step of the fixed horizon.This verifies the nondegeneracy needed for the Gaussian result after perturbation.Source: §B.1 · p. 32
  • Perturbing the maps by ε avoids degenerate Gaussian inputs at a fixed horizon, and the Gaussian recursion transfers back as ε tends to zero.The transfer uses continuity of the positive-semidefinite square root and requires no uniform lower bound on covariance eigenvalues.Source: §B.1 · pp. 31–32

B.2 An almost-sure truncation observation

  • Under uniform moments of all orders, truncation at n^κ eventually changes no entries almost surely, with centering and standardization errors decaying at arbitrary polynomial rates.An almost-sure state-evolution conclusion additionally requires an almost-sure limit for the comparison trajectory or summable probability errors.Source: §B.2 · p. 33

C The Comparison Estimate and Its Relation to Earlier Methods

The comparison estimate depends on differentiating with respect to the scaled matrix entry and controlling how replacement order changes intermediate derivatives. Moment comparisons establish convergence to a deterministic Gaussian limit, but do not couple empirical statistics or provide polynomial rates for C1 maps.

C.1 Which variable is differentiated

  • Differentiating with respect to Cab = Uab/√n makes matrix-entry moments scale as n^-r/2, giving cubic coefficients at n^-3/2 and fourth-order remainders at n^-2.The passage identifies this as the chain-rule scaling for the Taylor expansion.Source: §C.1 · p. 33
  • Fixed replacement orders evaluate cubic derivatives at different intermediate matrices, so deterministic bounds alone do not guarantee convergence.Proposition 4.7 bounds a sum at a common matrix; Identity (39) and Lemma 4.8 bound the displacement term, which is of the same order as the Taylor remainder.Source: §C.1 · p. 33

C.2 First, second, and centered fourth moments

  • For bounded statistics, comparison with a deterministic Gaussian limit requires first- and second-raw-moment comparisons, while centered fourth moments involve raw moments through order four.Theorem 4.9 bounds arbitrary polynomials, and Proposition 7.1 evaluates powers up to four.Source: §C.2 · p. 33
  • The estimates compare distributions and moments, not coupled random variables; convergence is shown through E(H − c)^2 for a deterministic Gaussian limit c.They do not specify a coupling between empirical statistics.Source: §C.2 · p. 33
  • The O(n^-1/2+ε) comparison bound leaves a Gaussian finite-size remainder, and smoothing yields qualitative convergence for C1 maps without a polynomial rate.A polynomial rate would require a quantitative approximation modulus.Source: §C.2 · p. 33

C.3 Derivative estimates and moment methods

The section contrasts the aggregate derivative estimate with earlier methods and clarifies the hypotheses and scope of the proof. Its probabilistic inputs apply to independent rectangular entries at a fixed time horizon; other geometries and settings require separate proofs.

C.3 Derivative estimates and moment methods

  • Unlike the symmetric-matrix approach in [4, Sections 5–6], the aggregate estimate handles same-index and mixed branching terms for independent rectangular entries and empirical observables.The Schur-product norm bound controls same-index terms, while the Frobenius bound (27) controls mixed terms.Source: §C.3 · p. 33
  • The cited theorem in [6, Definition 2.18 and Theorem 2.21] assumes variance-balance, spectral, and side-information hypotheses, and Examples 8.1 and 8.6 distinguish its condition from this paper's uniform fourth-moment condition.Example 8.1 fails the cited condition at p = 5; Example 8.6 satisfies it but fails this paper's uniform fourth-moment condition.Source: §C.3 · p. 34
  • The model in permits correlations between transposed entries, while non-separable iterations are treated in [7].The cited moment-growth and sparsity conditions apply to the non-symmetric geometry in.Source: §C.3 · p. 34
  • The proof uses Gaussian state evolution and independent-entry operator-norm bounds, without external non-Gaussian universality theorems; its time horizon is fixed.Growing iteration counts, alternative convergence modes, and dependent matrices require separate proofs.Source: §C.3 · p. 34

Related papers

Loading 2610.28971v1…