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
2004000
0.50
0.11
0.15
0.050.4
40
1060
20
540

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