Source-linked AI summary
State Evolution for General Approximate Message Passing Algorithms, with Applications to Spatial Coupling
Adel Javanmard, Andrea Montanari
TL;DR
The paper addresses how to rigorously characterize the high-dimensional behavior of broad AMP algorithms when Gaussian matrix entries are independent but not identically distributed. It generalizes state evolution and proves a framework covering generalized AMP and spatially coupled sensing, including prior spatial-coupling reconstruction results.
Problem
Existing state-evolution results covered restricted matrix and function classes, while generalized AMP and spatially coupled sensing required broader rigorous analysis.
Method
The paper develops a rigorous generalized state-evolution framework for AMP, using matrix-valued, row-separable iterations and a proof reduction from rectangular to symmetric Gaussian matrices.
Results
AMP's high-dimensional behavior admits an exact asymptotic Gaussian description, and the framework covers generalized AMP and spatially coupled sensing applications.
Takeaways & Limitations
State evolution provides a rigorous common analysis for these AMP applications, including spatially coupled reconstruction at the information-theoretic threshold δ > d(pX).
Takeaways & Limitations
The main theorem assumes locally Lipschitz coordinate functions and a symmetric Gaussian matrix construction, with rectangular cases handled by reduction.
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 \cite{BM-MPCS-2011}, while simplifying and generalizing several steps.
1 Introduction
The paper develops a rigorous generalization of AMP state evolution for Gaussian matrices and uses it to cover generalized AMP and spatially coupled sensing. Its framework unifies several applications through a matrix-valued, row-separable iteration, while robust-regression applications remain future work.
- AMP and state evolution: AMP algorithms have an exact high-dimensional description: at fixed iteration, their state vectors become asymptotically Gaussian, with variances characterized by state evolution.Earlier proofs covered i.i.d. Gaussian matrices with Lipschitz separable functions, while related extensions treated independent non-Gaussian entries under polynomial assumptions.
- Generalized AMP: Generalized AMP extends AMP to nonlinear estimation through memoryless observation channels, for which suitable state-evolution equations had been conjectured without a formal proof.The linear Gaussian-noise model is recovered as a special case.
- Spatial coupling: For spatial coupling, sensing matrices have independent centered Gaussian entries with non-identical variances, including block-variance structures that are band-diagonal in the spatially coupled case.The row and column indices are partitioned into groups, with variances determined by the corresponding groups.
- Spatial coupling: A prior rigorous analysis showed that AMP reconstructs signals with high probability when the undersampling rate satisfies δ > d(pX), and that reconstruction is robust to noise [DJM11b].Here d(pX) is the upper Rényi information dimension of pX.
- Paper contribution: The paper establishes a rigorous state-evolution generalization covering the developments discussed, including generalized AMP and spatially coupled sensing matrices.Applications to robust regression are explicitly left for future study.
- Generalized iteration: The generalized iteration replaces vector states by fixed-width matrices, uses functions separable across rows, and replaces scalar memory coefficients with q × q matrices.The proof simplifies the analysis by reducing rectangular-matrix recursions to a symmetric-matrix recursion with a single vector state.
2 Main result
The main result defines AMP on a vector space with locally Lipschitz coordinate maps and establishes state evolution for converging sequences of instances. Under the stated moment and convergence conditions, low-dimensional AMP marginals are asymptotically Gaussian with covariance determined by the state-evolution recursion.
- 2 Main result: AMP operates on Vq,N ≡ (Rq)^N ≃ RN×q, with matrix multiplication acting through the natural coordinatewise vector-space representation.The matrix action is identified with the Kronecker product A ⊗ Iq×q.
- 2 Main result: A symmetric AMP instance consists of A = G + G^T, locally Lipschitz coordinate functions, and an initial condition x0.The Gaussian matrix construction uses i.i.d. entries Gij drawn from N(0, (2N)^−1).
- 2 Main result: The AMP orbit is defined as a sequence of vectors indexed by iteration, and rectangular AMP recursions can be recast in the symmetric framework covered by Theorem 1.This reduction is the bridge from the symmetric main theorem to rectangular matrices.
- 2 Main result: Converging AMP-instance sequences use a fixed q, Lipschitz limiting functions, q limiting probability measures, proportional coordinate partitions, and empirical-distribution convergence within each partition.The partition can be refined or augmented with dummy coordinates without loss of generality, and yi remains fixed across iterations.
- 2.1 State evolution: State evolution characterizes the covariance of AMP's asymptotically Gaussian low-dimensional marginals through positive semidefinite matrices Σt.The covariance recursion is defined separately for each iteration t ≥ 1.
- 2.1 State evolution: Theorem 1 establishes almost-sure state-evolution limits for pseudo-Lipschitz observables of AMP iterates under moment and convergence assumptions.The theorem applies for every fixed iteration, coordinate, and pseudo-Lipschitz test function of the specified order.
3 AMP for rectangular and spatially-coupled matrices
The paper applies its general state-evolution theorem to rectangular AMP and spatially coupled compressed-sensing matrices. It defines a block-structured Gaussian ensemble, constructs the AMP denoisers and state evolution, and proves the resulting asymptotic characterization.
- Rectangular matrices: Rectangular AMP iterations are recast as symmetric-matrix iterations, bringing them under the scope of Theorem 1.The construction embeds the rectangular dynamics into a converging symmetric AMP instance with dimension N = m + n and q = Lr + Lc.
- Applications: Theorem 1 is applied to AMP reconstruction with spatially coupled matrices, implying Lemma 4.1 in [DJM11b].The proof establishes the claimed asymptotic state-evolution description of the reconstruction algorithm.
- General matrix ensemble: The ensemble partitions rows and columns into Lr and Lc equal-sized groups, with dimensions m = m0Lr and n = n0Lc.Independent Gaussian entries are assigned variances according to the group pair, and spatial coupling corresponds to a band-diagonal block-variance structure.
- Spatial coupling: Spatially coupled sensing matrices use blockwise Gaussian variances, with blocks on the same diagonal sharing variance when the variance profile depends on group distance.The matrix is divided into m0 by n0 blocks, and the coupling profile determines the variance of each block.
- AMP construction: The compressed-sensing AMP denoiser is differentiable, acts entrywise, and depends on the signal distribution pX; its group-specific conditional-expectation form is used in the construction.The state evolution can be precomputed and supplies the parameters used to define ηt, Qt, and bt.
- Proof: Applying Theorem 1 to the constructed symmetric instances yields almost-sure asymptotic identities for the spatially coupled AMP orbit.The proof proceeds by matching the rectangular algorithm to selected coordinates of the symmetric orbit and verifying the required relations by induction.
4 Proof of Theorem 1
The proof tracks AMP iterates through conditional Gaussian distributions and induction, establishing state-evolution limits for pseudo-Lipschitz observables under moment and non-degeneracy conditions.
- Conditional-distribution strategy: The proof computes the conditional distribution of each next iterate given the filtration generated by previous iterates, observations, and messages.This conditions on the matrix through the induced filtration rather than conditioning on the matrix directly.
- Non-triviality reduction: The non-triviality condition excludes degenerate limits, while a bounded smooth perturbation handles non-triviality failures and is removed by continuity as ε → 0.The perturbed orbit satisfies state evolution, and the relevant observables differ from the original ones by at most Cε.
- Inductive proof: The induction maintains projection decompositions, Gaussian conditional laws, empirical limits, and inner-product identities across iterations.The induction property includes equations governing state-evolution moments, cross-correlations, Jacobian averages, and norm limits.
- Induction basis: At the induction basis, x1 = Am0 has Gaussian coordinate limits Za ∼ N(0, Σ1) independent of Ya, and its empirical distribution converges accordingly.The covariance is identified from the quadratic form limit ⟨Am0, Am0⟩ → Σ1.
A Reference probability results
The appendix collects probability results used in the proof, including strong laws for independent non-identically distributed arrays, Gaussian-matrix properties, Stein’s lemma, and pseudo-Lipschitz convergence.
- Strong laws: Theorem 2 gives an almost-sure strong law for centered triangular arrays of mutually independent variables under a 2+κ moment-growth condition.The normalized sum converges to zero as the array size tends to infinity.
- Gaussian matrices: Lemma 4 records Gaussian-matrix projection and norm properties for deterministic vectors and subspaces, generalizing the cited prior lemma.It supports the distributional and concentration calculations used for AMP iterates.
- Gaussian identities: Stein’s lemma relates jointly Gaussian variables to derivatives of test functions, enabling Jacobian-based identities in the AMP proof.The lemma is stated for vector-valued functions under the required integrability conditions.
- Pseudo-Lipschitz convergence: Lemma 6 extends the law of large numbers to pseudo-Lipschitz functions when empirical distributions and corresponding k-th moments converge.This converts empirical averages into expectations under the limiting probability measure.