Source-linked AI summary
State Evolution for General Approximate Message Passing Algorithms, with Applications to Spatial Coupling
Adel Javanmard, Andrea Montanari
TL;DR
AMP algorithms lack a simple high-dimensional analysis in many estimation settings, motivating a suitable state-evolution description. This paper rigorously establishes such a generalization for Gaussian matrices with independent, possibly non-identically distributed entries, covering generalized AMP and spatially coupled compressed sensing.
Problem
Existing rigorous state-evolution results were limited by matrix and function assumptions, while generalized AMP and spatially coupled sensing required broader analysis.
Method
The paper analyzes a generalized AMP recursion using a proof based on, simplifying it through a symmetric-matrix formulation and reducing rectangular matrices to that case.
Results
The resulting state-evolution theorem characterizes AMP’s high-dimensional behavior and applies to Gaussian matrices with independent, non-identically distributed entries, including generalized AMP and spatially coupled sensing.
Takeaways & Limitations
State evolution provides a rigorous asymptotic analysis for the covered AMP algorithms and spatially coupled sensing constructions.
Takeaways & Limitations
The main theorem assumes locally Lipschitz coordinate functions and Gaussian matrix entries with zero mean and group-dependent variances.
Abstract
from arXiv · showhide
We consider a class of approximated message passing (AMP) algorithms and characterize their high-dimensional behavior in terms of a suitable state evolution recursion. Our proof applies to Gaussian matrices with independent but not necessarily identically distributed entries. It covers --in particular-- the analysis of generalized AMP, introduced by Rangan, and of AMP reconstruction in compressed sensing with spatially coupled sensing matrices. The proof technique builds on the one of [BM11], while simplifying and generalizing several steps.
1 Introduction
The paper develops a rigorous state-evolution framework for AMP algorithms, extending prior results to generalized AMP and Gaussian matrices with independent, non-identically distributed entries. It also connects the framework to spatially coupled compressed sensing and related AMP applications.
- AMP combines ideas from belief propagation and statistical physics to estimate signals in problems lacking sparse graphical-model descriptions.
- State evolution gives AMP’s high-dimensional behavior an exact description through a one-dimensional recursion with asymptotically Gaussian iterates.
- The framework covers generalized AMP for nonlinear estimation through memoryless observation channels, extending beyond the additive-noise linear model.
- For spatially coupled sensing matrices, prior work showed that AMP reconstruction reaches the information-theoretic limit under an undersampling condition.
- The paper generalizes state evolution for Gaussian matrices whose independent entries may have non-identical variances, including block-structured spatially coupled matrices.
- The proof builds on, simplifies the analysis by using a symmetric-matrix recursion, and reduces rectangular matrices to that setting.
2 Main result
The main result formalizes AMP on fixed-width vector spaces and establishes Gaussian low-dimensional marginals whose covariance is determined by state evolution. The theorem applies to converging sequences of instances under regularity and moment assumptions.
- AMP operates on Vq,N ≡ (Rq)N ≃ RN×q, with matrices acting naturally across the N vector components.
- A symmetric AMP instance consists of a random symmetric Gaussian matrix, locally Lipschitz coordinate functions, and an initial condition.
- The AMP orbit is the sequence of iterates generated from the instance by the paper’s recursive update definition.
- Converging instance sequences use a fixed coordinate width, group-specific limiting distributions, positive definite covariance matrices, and asymptotically stable group proportions.
- 2.1 State evolution: State evolution assigns a positive semidefinite covariance matrix to each iteration and characterizes the covariance of the iterates’ low-dimensional marginals.
- 2.1 State evolution: Under bounded moment and empirical-convergence assumptions, pseudo-Lipschitz observables of the iterates converge almost surely to their state-evolution predictions.
3 AMP for rectangular and spatially-coupled matrices
The section extends AMP state-evolution analysis from symmetric settings to rectangular matrices and applies it to spatially coupled compressed sensing. It constructs a general block-variance Gaussian ensemble, specifies the corresponding AMP and state evolution, and derives the spatial-coupling result from the main theorem.
- 3 AMP for rectangular and spatially-coupled matrices: Rectangular AMP iterations are recast as iterations with a symmetric matrix, allowing the rectangular case to be covered by Theorem 1.The construction embeds the rectangular problem in dimensions N = m + n with q = Lr + Lc.
- 3.1 General matrix ensemble: The general ensemble M(W, m0, n0) uses independent Gaussian entries whose variances are determined by row and column groups through a nonnegative matrix W.Rows and columns are partitioned into Lr and Lc equal-sized groups, with m = m0Lr and n = n0Lc.
- 3.1 General matrix ensemble: Spatially coupled sensing matrices are represented by a special band-diagonal structure of the block variances, with equal variances along blocks on each diagonal when weights depend on group distance.The matrix is divided into m0 by n0 blocks, and its entries have variance scaled by Wg(i),g(j).
- 3.2 AMP for compressed sensing reconstruction: The compressed-sensing AMP uses differentiable, componentwise nonlinearities ηt that depend on the signal distribution pX and vary parametrically by column group.The associated state-evolution sequence can be precomputed and is used to define ηt, Qt, and bt.
- 3.3 State evolution: Theorem 1 implies the state-evolution lemma asserting exact asymptotic analysis of the spatially coupled AMP algorithm in the large-dimension limit.The construction applies the theorem to a normalized matrix and the resulting orbit, under assumptions including m0/n0 → δ and convergent empirical distributions with bounded second moments.
4 Proof of Theorem 1
The proof establishes Theorem 1 by tracking conditional Gaussian behavior through the AMP iteration and verifying the required empirical limits inductively. A perturbation argument extends the result from non-trivial denoisers to general Lipschitz functions.
- Conditional analysis: The proof computes the conditional distribution of x_{t+1} given the filtration generated by prior iterates and messages, conditioning instead on the matrix A.The conditional law of A is characterized relative to this filtration.
- Conditional analysis: Orthogonal projections of m_t onto earlier message spaces organize the dependence structure needed for the induction.The projected components and their coefficient matrices are introduced to express the AMP equations in matrix form.
- Removing non-triviality: A bounded smooth perturbation makes a degenerate denoiser sequence non-trivial, after which continuity and dominated convergence transfer state evolution back as the perturbation vanishes.The perturbation orbit converges to the original orbit through bounds uniform in N.
- Inductive limits: The main technical lemma yields bounded, deterministic limiting matrices and Gaussian asymptotic variables independent of the associated observations.These limits support the state-evolution description of empirical observables.
- Inductive limits: Stein-type identities convert empirical inner products involving iterates and Lipschitz transforms into products of covariance limits and averaged Jacobians.The key identity is expressed as lim_N→∞⟨x_{r+1}, ϕ(x_{s+1}, y)⟩ = lim_N→∞⟨x_{r+1}, x_{s+1}⟩⟨∇ϕ(x_{s+1}, y)⟩.
A Reference probability results
The appendix collects probability tools used in the proof, including strong laws for independent non-identically distributed triangular arrays, Gaussian projection properties, Stein’s lemma, and pseudo-Lipschitz convergence.
- Strong laws: The triangular-array strong law handles mutually independent, non-identically distributed variables under a uniform 2+κ moment-growth condition.Under the stated bound, normalized sums converge almost surely to zero.
- Gaussian matrix facts: A Gaussian projection lemma describes the projection of a transformed Gaussian matrix onto a fixed-dimensional subspace as D x, with x vanishing almost surely.The result applies when the deterministic input has normalized covariance Iq×q.
- Gaussian identities: Stein’s lemma relates expectations involving jointly Gaussian vectors to derivatives of the test function.This identity supplies the Gaussian integration-by-parts step used in the proof.
- Empirical convergence: A generalized law of large numbers applies pseudo-Lipschitz functions to vector sequences whose empirical distributions and kth moments converge.The finite kth-moment condition controls the unbounded test functions used in state-evolution limits.