State Evolution

What State Evolution Delivers

The payoff for introducing the Onsager term is that AMP admits a one-dimensional deterministic description of its per-iteration performance in the large-system limit. This description β€” state evolution (SE) β€” is a scalar recursion Ο„t+12=Ξ¨(Ο„t2)\tau_{t+1}^2 = \Psi(\tau_t^2) whose fixed points predict the terminal MSE, the convergence speed, and the sharp phase-transition boundary between recoverable and unrecoverable signals.

The analytical power is considerable: we can predict AMP's MSE without running AMP, plot phase diagrams by sweeping (δ,ρ)(\delta,\rho), and design denoisers by minimising a scalar function.

Theorem: State Evolution (Bayati--Montanari)

Consider AMP with denoiser Ξ·\eta on the model of Definition DLinear Observation Model, with N,Mβ†’βˆžN, M \to \infty at fixed Ξ΄=M/N\delta = M/N. Assume Ξ·(β‹…;ΞΈ)\eta(\cdot;\theta) is Lipschitz and the prior pXp_X has finite second moment. Then, for every iteration tβ‰₯0t \ge 0:

(a) Gaussianity of pseudo-data. In the sense of empirical distribution convergence, AHrt+x^tβ€…β€Š=dβ€…β€Šx+Ο„tZ,Z∼N(0,IN),ZβŠ₯x.\mathbf{A}^{H}\mathbf{r}^t + \hat{\mathbf{x}}^t \;\stackrel{d}{=}\; \mathbf{x} + \tau_t \mathbf{Z}, \qquad \mathbf{Z} \sim \mathcal{N}(\mathbf{0},\mathbf{I}_N), \quad \mathbf{Z} \perp \mathbf{x}.

(b) Scalar recursion. The variance Ο„t2\tau_t^2 evolves as Ο„t+12β€…β€Š=β€…β€ŠΟƒ2β€…β€Š+β€…β€Š1δ E ⁣[(Ξ·(X+Ο„tZ;ΞΈt)βˆ’X)2],\boxed{\tau_{t+1}^2 \;=\; \sigma^2 \;+\; \frac{1}{\delta}\,\mathbb{E}\!\left[\bigl(\eta(X+\tau_t Z;\theta_t) - X\bigr)^2\right],} with Ο„02=Οƒ2+1Ξ΄E[X2]\tau_0^2 = \sigma^2 + \frac{1}{\delta}\mathbb{E}[X^2], X∼pXX \sim p_X, Z∼N(0,1)Z \sim \mathcal{N}(0,1) independent.

Part (a) says that AMP behaves as if at every iteration we were denoising the signal x\mathbf{x} observed in an AWGN channel of variance Ο„t2\tau_t^2. Part (b) is Pythagoras: the effective noise variance at the next iteration equals the physical noise Οƒ2\sigma^2 plus a rescaling (1/Ξ΄1/\delta) of the scalar MSE achieved by the denoiser at the previous iteration.

Proof
Conditioning on the iterates (cavity argument)

Denote by Ft\mathbb{F}_t the Οƒ\sigma-algebra generated by {x^s,rs}s≀t\{\hat{\mathbf{x}}^s, \mathbf{r}^s\}_{s \le t}. By the orthogonality of Gaussian projections, conditioning A\mathbf{A} on Ft\mathbb{F}_t leaves the complementary random projection Gaussian. This is the same cavity-method argument used in the TAP analysis of the SK model.

Onsager cancels the bias

Writing AHrt\mathbf{A}^{H}\mathbf{r}^t as a sum of independent terms conditioned on Ft\mathbb{F}_t yields a linear combination of Gaussian increments plus a systematic bias Ξ΄βˆ’1βŸ¨Ξ·β€²(utβˆ’1)βŸ©β€‰rtβˆ’1\delta^{-1}\langle\eta'(u_{t-1})\rangle\,\mathbf{r}^{t-1}. The Onsager term in the AMP residual is constructed to cancel this bias exactly, leaving a pure Gaussian.

Variance bookkeeping

The residual rt\mathbf{r}^t has entries with variance Ο„t2Ξ΄\tau_t^2 \delta (the factor Ξ΄\delta comes from Eβˆ₯rtβˆ₯2/M\mathbb{E}\|\mathbf{r}^t\|^2/M). Hence AHrt+x^tβˆ’x\mathbf{A}^{H}\mathbf{r}^t + \hat{\mathbf{x}}^t - \mathbf{x} is a Gaussian of per-entry variance Ο„t2\tau_t^2. The denoiser is then applied, producing error E[(Ξ·(X+Ο„tZ;ΞΈt)βˆ’X)2]\mathbb{E}[(\eta(X+\tau_t Z;\theta_t)-X)^2] per coordinate. Plugging this back through the residual update gives the claimed recursion.

Passage to the limit

Bayati--Montanari (2011) rigorously show that, for Lipschitz Ξ·\eta, the empirical distribution of (x^t,x,AHrt)(\hat{\mathbf{x}}^t, \mathbf{x}, \mathbf{A}^{H}\mathbf{r}^t) converges almost surely to the joint distribution (Ξ·(X+Ο„tZ;ΞΈt),X,X+Ο„tZ)(\eta(X+\tau_t Z;\theta_t), X, X+\tau_t Z) in Wasserstein-2 sense. This upgrades the heuristic cavity argument into a theorem.

,

Definition:

State-Evolution Fixed Point

A fixed point of state evolution is a value τ⋆2β‰₯0\tau^2_\star \ge 0 with τ⋆2=Οƒ2+1δ E ⁣[(Ξ·(X+τ⋆Z;θ⋆)βˆ’X)2].\tau^2_\star = \sigma^2 + \frac{1}{\delta}\,\mathbb{E}\!\left[(\eta(X+\tau_\star Z;\theta_\star)-X)^2\right]. Define Ξ¨(Ο„2)=Οƒ2+Ξ΄βˆ’1E[(Ξ·(X+Ο„Z;ΞΈ(Ο„))βˆ’X)2]\Psi(\tau^2) = \sigma^2 + \delta^{-1}\mathbb{E}[(\eta(X+\tau Z;\theta(\tau))-X)^2]. A fixed point is stable if Ξ¨β€²(τ⋆2)<1\Psi'(\tau^2_\star) < 1 and unstable otherwise.

When Ξ¨\Psi has multiple fixed points, AMP generically converges to the stable fixed point encountered first by the iteration β€” typically the one with the largest Ο„2\tau^2. This is why AMP can miss the global optimum even when state evolution admits a smaller fixed point.

Theorem: AMP MSE Equals State-Evolution Fixed Point

Under the hypotheses of Theorem TState Evolution (Bayati--Montanari), let τ⋆2=lim⁑tβ†’βˆžΟ„t2\tau^2_\star = \lim_{t\to\infty} \tau_t^2 be the limit of the SE recursion. Then lim⁑Nβ†’βˆž1Nβˆ₯x^βˆžβˆ’xβˆ₯2β€…β€Š=β€…β€ŠE ⁣[(Ξ·(X+τ⋆Z;θ⋆)βˆ’X)2]β€…β€Š=β€…β€ŠΞ΄β€‰(τ⋆2βˆ’Οƒ2),\lim_{N\to\infty}\frac{1}{N}\|\hat{\mathbf{x}}^\infty - \mathbf{x}\|^2 \;=\; \mathbb{E}\!\left[(\eta(X+\tau_\star Z;\theta_\star)-X)^2\right] \;=\; \delta\,(\tau_\star^2 - \sigma^2), almost surely.

The terminal MSE of AMP is determined entirely by the one scalar τ⋆2\tau^2_\star β€” a remarkable dimensionality reduction from an NN-dimensional distribution to a single number.

Proof
Convergence of the recursion

Ξ¨\Psi is monotone (a mixture of MSE curves, each monotone in input noise) and bounded, so Ο„t2\tau_t^2 is monotone in tt and converges to τ⋆2\tau^2_\star. Since Ξ¨\Psi is continuous, the limit is a fixed point.

Passing limits inside

By Lipschitz continuity of Ξ·\eta, the expectation E[(Ξ·(X+Ο„Z;ΞΈ)βˆ’X)2]\mathbb{E}[(\eta(X+\tau Z;\theta)-X)^2] is continuous in Ο„\tau. Combined with the empirical-distribution convergence from Theorem TState Evolution (Bayati--Montanari), we obtain the stated equality almost surely.

Connection to the Replica Prediction

If Ξ·\eta is the MMSE denoiser for the prior pXp_X matched to effective noise Ο„2\tau^2, the state-evolution fixed point coincides with the replica-symmetric prediction of the Bayes-optimal MMSE, which is conjectured (and in many cases proved, e.g.\ Reeves--Pfister 2016) to be the fundamental information-theoretic limit of the Bayesian CS problem.

In other words: when AMP converges, AMP matched to the prior is asymptotically Bayes-optimal. This elevates AMP from a heuristic iterative solver to a provably optimal estimator in the proportional asymptotic regime.

Example: State Evolution, Noiseless LASSO, and the Donoho--Tanner Curve

Take Οƒ2=0\sigma^2 = 0 and a sparse signal with i.i.d. entries from (1βˆ’Ο)Ξ΄0+ρpβ‰ 0(1-\rho)\delta_0 + \rho p_{\neq 0}. Using AMP with soft-thresholding tuned optimally, derive the state-evolution fixed-point equation and identify the boundary between successful and failed recovery.

Solution
Scalar MMSE of the soft-threshold

Let msest(Ο„2;Ξ»)=E[(Ξ·st(X+Ο„Z;λτ)βˆ’X)2]\mathrm{mse}_{\mathrm{st}}(\tau^2;\lambda) = \mathbb{E}[(\eta_{\mathrm{st}}(X+\tau Z;\lambda\tau)-X)^2] be the scalar MSE of soft-thresholding on the Bernoulli--Gaussian signal with threshold λτ\lambda\tau. Direct computation (integrating the Gaussian density against the piecewise-linear soft-threshold) gives a closed-form expression depending on ρ\rho and Ξ»\lambda only.

Normalised SE recursion

With Οƒ2=0\sigma^2=0 the recursion becomes Ο„t+12=1δ msest(Ο„t2;Ξ»t).\tau_{t+1}^2 = \frac{1}{\delta}\,\mathrm{mse}_{\mathrm{st}}(\tau_t^2;\lambda_t). Scaling: msest(Ο„2;λτ)=Ο„2M(ρ,Ξ»)\mathrm{mse}_{\mathrm{st}}(\tau^2;\lambda\tau) = \tau^2 M(\rho,\lambda) for a function MM independent of Ο„\tau. The recursion is then Ο„t+12=Ξ΄βˆ’1M(ρ,Ξ») τt2\tau_{t+1}^2 = \delta^{-1} M(\rho,\lambda)\,\tau_t^2, a geometric decrease iff M(ρ,Ξ»)/Ξ΄<1M(\rho,\lambda)/\delta < 1.

Phase transition

Optimising over Ξ»\lambda for each (Ξ΄,ρ)(\delta,\rho) yields the Donoho--Tanner phase boundary ρDT(Ξ΄)=maxβ‘Ξ»Ξ΄βˆ’M(ρ,Ξ»)const,\rho_{\mathrm{DT}}(\delta) = \max_\lambda \frac{\delta - M(\rho,\lambda)}{\mathrm{const}}, i.e., the curve of (Ξ΄,ρ)(\delta,\rho) below which M⋆(ρ)/Ξ΄<1M^\star(\rho)/\delta<1 and AMP converges to Ο„=0\tau=0 (exact recovery) and above which the iteration has a nonzero stable fixed point Ο„>0\tau>0 (recovery fails). This curve matches exactly the Donoho--Tanner combinatorial geometry result on phase transitions of β„“1\ell_1 recovery.

State Evolution vs Empirical AMP

Compares the scalar state-evolution prediction Ο„t2\tau_t^2 (deterministic recursion) against the empirical per-iteration MSE from a single run of AMP at finite NN. As NN grows the two curves lock onto each other.

Parameters
1000
0.5
0.15
40
20

Phase Transition Diagram

State-evolution phase diagram in the (Ξ΄,ρ)(\delta,\rho) plane for noiseless sparse recovery with a Bernoulli--Gaussian signal. Colour = predicted terminal MSE of AMP with optimally tuned soft-thresholding. The curve separates the "recovery" and "failure" regions β€” the Donoho--Tanner phase boundary.

Parameters

State-Evolution Cobweb Diagram

Animated cobweb plot of Ο„t+12=Ξ¨(Ο„t2)\tau_{t+1}^2 = \Psi(\tau_t^2) showing the iteration climbing (or descending) to its fixed point. For (Ξ΄,ρ)(\delta,\rho) below the DT curve the recursion descends to Ο„=0\tau=0; above it settles on a positive fixed point.
State-evolution trajectory: stable fixed points act as attractors for the AMP variance.

Common Mistake: State Evolution Is an Asymptotic Statement

Mistake:

Reading off the SE prediction for a specific finite-NN problem and being surprised when AMP's empirical MSE differs by 20% or more. Worse, tuning Ξ»\lambda assuming SE holds exactly at N=100N=100.

Correction:

State evolution predicts Ο„t2\tau_t^2 in the limit Nβ†’βˆžN \to \infty. For N≲500N \lesssim 500 deviations of 5--15% are normal. For N=2000N=2000-50005000 the agreement is typically tight (<2%). Always sanity-check by running AMP at two values of NN and confirming the empirical trajectories are converging to the SE prediction as NN grows.

State Evolution as a Diagnostic Tool

Beyond its role as a performance predictor, state evolution is useful as a diagnostic. If AMP's empirical MSE diverges from the SE prediction, one of the assumptions has been violated β€” typically: (i) the matrix A\mathbf{A} is not i.i.d.\ (Section 20.4); (ii) NN is too small; (iii) the denoiser is not Lipschitz. Each produces a characteristic signature that an experienced practitioner learns to recognise.

Key Takeaway

State evolution reduces the analysis of AMP β€” a random, high-dimensional, nonlinear dynamical system β€” to a one-dimensional deterministic recursion Ο„t+12=Οƒ2+Ξ΄βˆ’1E[(Ξ·(X+Ο„tZ)βˆ’X)2]\tau^2_{t+1} = \sigma^2 + \delta^{-1}\mathbb{E}[(\eta(X+\tau_t Z)-X)^2]. This is the most striking analytical feature of AMP and the reason phase transitions and Bayes-optimality can be computed in closed form.

AMP from First PrinciplesDenoiser Design for AMP