PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalized Approximate Message Passing for Estimation with Random Linear Mixing

Sundeep Rangan

arXiv:1010.5141v2cs.IT

TL;DR

The paper addresses computationally difficult estimation from linear transforms followed by probabilistic measurements, where matrix mixing creates high-dimensional posterior calculations. It introduces GAMP as a scalar-and-transform approximation to loopy belief propagation and extends state evolution to characterize its asymptotic behavior for large Gaussian i.i.d. matrices. The method supports broad input and output distributions, but its variants require those true distributions to be known.

  • Problem

    General linear mixing couples components so that posterior distributions for individual variables generally require difficult high-dimensional integrals.

  • Method

    GAMP iteratively decomposes vector estimation into scalar operations and linear transforms, approximating both sum-product and max-sum loopy belief propagation.

  • Results

    For large Gaussian i.i.d. transforms, state-evolution equations characterize GAMP's asymptotic componentwise behavior and predict componentwise performance metrics.

  • Takeaways & Limitations

    GAMP offers a computationally tractable methodology for a broad class of non-Gaussian linear-mixing estimation problems with asymptotic performance characterization.

  • Takeaways & Limitations

    Both sum-product and max-sum GAMP require the true input and output-channel distributions to be known.

Abstract

from arXiv · show

We consider the estimation of an i.i.d.\ random vector observed through a linear transform followed by a componentwise, probabilistic (possibly nonlinear) measurement channel. A novel algorithm, called generalized approximate message passing (GAMP), is presented that provides computationally efficient approximate implementations of max-sum and sum-problem loopy belief propagation for such problems. The algorithm extends earlier approximate message passing methods to incorporate arbitrary distributions on both the input and output of the transform and can be applied to a wide range of problems in nonlinear compressed sensing and learning. Extending an analysis by Bayati and Montanari, we argue that the asymptotic componentwise behavior of the GAMP method under large, i.i.d. Gaussian transforms is described by a simple set of state evolution (SE) equations. From the SE equations, one can \emph{exactly} predict the asymptotic value of virtually any componentwise performance metric including mean-squared error or detection accuracy. Moreover, the analysis is valid for arbitrary input and output distributions, even when the corresponding optimization problems are non-convex. The results match predictions by Guo and Wang for relaxed belief propagation on large sparse matrices and, in certain instances, also agree with the optimal performance predicted by the replica method. The GAMP methodology thus provides a computationally efficient methodology, applicable to a large class of non-Gaussian estimation problems with precise asymptotic performance guarantees.

I. INTRODUCTION

The paper introduces GAMP to make broad linear-mixing estimation problems computationally tractable while retaining approximations to both major forms of loopy belief propagation. For large Gaussian i.i.d. transforms, its behavior admits state-evolution characterization and componentwise performance prediction.

  • Motivation: General linear-mixing estimation couples transform-input components through A, making individual posterior distributions involve difficult high-dimensional integrals.With an identity transform, the problem decouples into scalar estimation problems; a general matrix instead couples x into z.
  • GAMP: GAMP decouples vector-valued estimation into a sequence of scalar problems and linear transforms.Its scalar estimation functions support Gaussian and quadratic approximations of loopy belief propagation.
  • Generality: GAMP accommodates essentially arbitrary input priors and output-channel distributions, including non-Gaussian inputs and output nonlinearities.It supports both max-sum approximations for MAP estimation and sum-product approximations for MMSE estimates and posterior marginals.
  • Computation: 10 to 20 iterations typically suffice for excellent convergence in the authors' simulations.The reported convergence behavior is empirical and concerns a small number of iterations.
  • State evolution: For large Gaussian i.i.d. transforms, simple state-evolution equations exactly describe asymptotic component behavior and predict componentwise metrics such as MSE or detection accuracy.The analysis extends earlier AMP-like results and agrees in certain instances with replica-method optimal-performance predictions.
  • Relation to loopy BP: GAMP provides a unified dense-matrix methodology for approximating both max-sum and sum-product loopy BP.The method builds on Gaussian and quadratic approximations that have been used in CDMA detection, lattice codes, compressed sensing, and related problems.

A. Computational Complexity

GAMP reduces each iteration to matrix transforms and scalar estimation functions, with per-iteration cost dominated by O(mn) matrix operations. Scalar-variance simplifications can reduce transforms per iteration from four to two while retaining the algorithm’s approximate message-passing structure.

  • Iteration structure: Each GAMP iteration alternates output and input linear transforms with componentwise nonlinear estimation steps.The procedure initializes estimates, performs output linear and nonlinear steps, then input linear and nonlinear steps before repeating.
  • Complexity: The worst-case complexity per iteration is O(mn), dominated by matrix-vector multiplications, and can be smaller for structured transforms.The paper specifically mentions Fourier, wavelet, and sparse transforms as examples.
  • Complexity: The number of iterations needed for the same per-component performance does not increase with problem size, so total complexity remains bounded by matrix-vector multiplication.This scaling claim is made in the state evolution discussion of the algorithm’s complexity.
  • Scalar-variance approximation: Replacing variance vectors with scalars can eliminate multiplications by |A|2 and (|A|2)T, reducing transforms per iteration from four to two.The approximation is heuristically justified for approximately equal-magnitude or large i.i.d. matrix components.
  • Inference modes: GAMP provides max-sum and sum-product loopy-BP approximations for MAP and MMSE estimation, respectively, including optimization problems whose functions need not derive from densities.The scalar estimation functions determine which loopy-BP approximation is implemented.
  • Inference modes: Max-sum GAMP reduces vector MAP estimation to sequential scalar MAP problems with effective Gaussian noise levels represented by τ_r(t) and τ_p(t).The scalar parameters characterize the effective noise in the input and output estimation problems.

B. Sum-Product GAMP for MMSE Estimation

Sum-product GAMP approximates loopy belief propagation for MMSE estimation by combining scalar input MMSE estimators with an output score-function computation. This turns vector estimation into a sequence of scalar problems involving effective Gaussian noise.

  • Input estimation: The MMSE estimate is the conditional expectation, and GAMP initializes from the prior mean and variance conditioned on q_j.The initialization uses no observations.
  • Input estimation: The sum-product input function is gin(b_r,q,τ_r) := E[X | b_R = b_r, Q = q], with derivative equal to the conditional variance.The derivative is ∂b_r gin(b_r,q,τ_r) := var[X | b_R = b_r, Q = q].
  • Output estimation: The output function is derived from the posterior density of Z given Y and computes an expectation over that scalar posterior.It also has an alternative score-function interpretation for the output-channel likelihood.
  • Overall procedure: Sum-product GAMP reduces vector MMSE estimation to scalar MMSE estimation at input nodes and an output score-function evaluation at output nodes.Both operations are performed as a sequence of scalar estimation problems from Gaussian noise.

C. AWGN Output Channels

For AWGN output channels, max-sum and sum-product GAMP use the same output update and reduce to the AMP update of Bayati and Montanari. The state-evolution analysis is formulated for large Gaussian i.i.d. transforms under explicit scaling and regularity assumptions.

  • AWGN specialization: For an AWGN output channel, the output posterior is Gaussian and the max-sum and sum-product output functions coincide.Their common output function is gout(b_p,y,τ_p) := (y − b_p)/(τ_p + τ_w).
  • AWGN specialization: The common output-function derivative is ∂b_p gout(b_p,y,τ_p) = 1/(τ_p + τ_w).The same derivative applies to both MAP and MMSE versions in the AWGN case.
  • AWGN specialization: Substituting the AWGN output equations into the input updates precisely recovers the original AMP algorithm, up to scaling.This equivalence holds for both max-sum and sum-product GAMP.
  • State evolution: State evolution describes GAMP behavior through scalar random variables for the input and output channels, whose expectations can be evaluated numerically.The equations are specified algorithmically using input-channel variables and an output-channel covariance model.
  • State-evolution assumptions: The state-evolution analysis assumes m scales linearly with n and A has i.i.d. Gaussian entries a_ij ∼ N(0,1/m).The measurement ratio is β > 0, and z = Ax.
  • State-evolution assumptions: The analysis also assumes convergent initial conditions and input sequences with bounded moments, an output model y_i = h(z_i,w_i), and pseudo-Lipschitz regularity of the estimation functions.These assumptions support the scalar state-evolution description of GAMP.

D. Main Result

For large i.i.d. Gaussian transforms, scalar state evolution exactly characterizes GAMP’s fixed-iteration component behavior and supports asymptotic performance prediction. The analysis also recovers earlier AMP results under special output-channel assumptions.

  • State evolution: Scalar state evolution parameters replace the variance vectors in the simplified GAMP algorithm and are computed through output-node and input-node updates.The procedure initializes τ_x(0), then alternates output and input updates over scalar random-variable models.
  • Claim 1: For every fixed iteration, τ_r(t) and τ_p(t) converge almost surely to deterministic limits under the stated assumptions.This is the first part of Claim 1 for scalar-variance GAMP.
  • Claim 1: At each fixed iteration, the empirical component distributions of (x, q, b_r) and (z, b_p, w, y) converge to the scalar random-variable models specified by state evolution.The input-side limit is θ_r(ξ_r(t), α_r(t)); the output-side limit is θ_p(K_p(t)).
  • Scalar equivalent model: The scalar equivalent model represents each GAMP input estimate as a nonlinear scalar function of a scaled, Gaussian-noise-corrupted signal and its side information.A corresponding interpretation applies at the output nodes.
  • Special cases: Under additive-noise assumptions, the general state evolution reduces to the established AMP state evolution for a general input function.The reduction follows when the output noise has variance τ_w and the relevant expectation is taken over the scalar input model.

B. Sum-Product GAMP with AWGN Output Channels

For AWGN outputs, sum-product GAMP’s state-evolution fixed points coincide with replica predictions for exact MMSE and MAP estimation, including mismatched input distributions. With matched distributions, the equations also extend sparse-matrix BP results to dense matrices.

  • Mismatched estimation: The sum-product GAMP analysis allows the estimator’s postulated input distribution to differ from the true distribution.The postulated MMSE and MAP estimators are defined using p^post_X|Q rather than necessarily matching p_X|Q.
  • MMSE fixed points: For AWGN outputs, the fixed points of the MMSE state-evolution updates precisely match Guo and Verdú’s replica equations for non-Gaussian-prior MMSE estimation.The comparison concerns exact MMSE estimation under the postulated prior, not merely the GAMP approximation.
  • Matched distributions: With matched distributions, the equations reduce to the state evolution previously derived for sum-product BP on large sparse random matrices.The matched-distribution case is obtained as a special case of the general equations.
  • MAP fixed points: For MAP estimation, the state-evolution fixed points precisely agree with replica equations for AWGN output noise and provide an algorithm associated with those predictions.The paper characterizes the scalar input update as a MAP estimate under the postulated model.
  • Scope extension: The same state-evolution equations therefore hold for dense matrices, while the framework additionally covers mismatched estimator distributions.The paper presents this as an extension of earlier sparse-matrix analyses.

VII. NONLINEAR COMPRESSED SENSING EXAMPLE

The nonlinear compressed sensing experiment compares GAMP using the true nonlinear output channel with a linear approximation, while testing state-evolution predictions. Modeling choices and results show a substantial benefit from incorporating nonlinearity and close agreement between simulation and state evolution.

  • Estimators: NL-GAMP matches the true input and output distributions, whereas Lin-GAMP matches the input but assumes a linear output channel.Both estimators use the full GAMP algorithm and are evaluated over 100 Monte Carlo simulations.
  • Results: NL-GAMP achieves an asymptotic gain of over 11 dB relative to Lin-GAMP's linear output approximation.The comparison uses normalized squared error for sparse-vector estimates.
  • State evolution: State evolution predicts median performance within 0.2 dB for Lin-GAMP and 0.4 dB for NL-GAMP.Although theory formally analyzes a modified simplified algorithm, the prediction also holds for the full algorithm in this simulation.
  • State evolution: The Lin-GAMP squared error increases slightly after iteration 7, and state evolution predicts this non-monotonic behavior.For NL-GAMP, the postulated and true distributions are matched; Lin-GAMP has mismatched nonlinear-output modeling.
  • Conclusion: The simulation demonstrates a tractable nonlinear compressed sensing approach with gains over linearized AMP and precise asymptotic performance characterization.The conclusion identifies GAMP as applicable to a broad class of linear-mixing estimation problems.

APPENDIX A VECTOR-VALUED AMP

The appendix formulates a vector-valued recursion for GAMP and states its state-evolution behavior under large i.i.d. Gaussian transforms. The result connects empirical algorithm variables to Gaussian vector limits, but its general proof is only sketched.

  • Recursion: The vector-valued recursion uses Lipschitz input and output functions over vector states and iterates indexed by t.The functions Gin and Gout operate on vector arguments, while the recursion generates b_i(t) and d_j(t).
  • Assumptions: The asymptotic setting assumes a deterministic output dimension scaling linearly with n and i.i.d. Gaussian transform entries a_ij ~ N(0, 1/m).The assumptions also include empirical convergence and bounded moments for relevant components.
  • State evolution: The state-evolution equations use expectations over limiting variables and Gaussian vectors independent of the associated parameters, with specified initialization.The matrices are obtained either empirically from the iterates or through expected values.
  • Asymptotic result: For any fixed iteration, the recursion variables converge empirically under either empirical or expected updates.The limiting representation uses Gaussian vectors B(t) and D(t) independent of θu and θv.
  • Proof status: Claim 1 follows rigorously from Claim 2’s stated implication, although Claim 2 itself is not fully rigorous because its vector-valued proof is only sketched.The appendix identifies a complete proof as future work and reserves the term Claim rather than Theorem.

APPENDIX C MAX-SUM GAMP

This appendix describes max-sum loopy belief propagation for MAP estimation and introduces the message representation and update structure that GAMP approximates.

  • Message passing: Max-sum loopy BP sends value-function messages between input nodes x_j and output nodes z_i.The messages are denoted Δ_i←j(t, x_j) and Δ_i→j(t, x_j).
  • Message passing: The output-node update maximizes over vectors x subject to a fixed component x_j and the linear constraint z_i = a_i^T x.Here a_i^T is the ith row of A, and terms independent of x_j may be discarded.
  • Message passing: The input-node update combines incoming messages to update the value associated with each x_j.The algorithm is initialized with reverse messages equal to zero and terminated after finitely many iterations.
  • Estimation: After the final iteration, the estimate of x_j is obtained by maximizing the resulting input-node value function.The final estimate is based on the maximum of the accumulated message representation.
  • Approximation tool: The appendix defines a quadratic variant of the Legendre transform to support the approximation analysis under differentiability and unique-maximizer assumptions.Lemma 1 supplies derivative identities for this transform.

C. GAMP Approximations

The paper derives GAMP as a first-order, quadratic approximation to max-sum loopy BP for MAP estimation. The approximation replaces message updates with the scalar input/output functions used by GAMP.

  • Quadratic approximation: GAMP approximates max-sum BP by expanding message terms around their current estimates and neglecting second-order terms in a_ij.The derivation uses local quadratic approximations of the messages.
  • Output update: The output-node approximation reduces the constrained maximization to a least-squares calculation involving the current message estimates.This produces the approximate output update after terms independent of z_i are removed.
  • Output update: Comparing the approximated output messages with the quadratic transform identifies the GAMP output function gout and its derivative.The resulting definitions agree with the corresponding GAMP quantities.
  • Input update: The input-node update is obtained by substituting the approximated output message and retaining first-order terms.The resulting expression matches the GAMP input function gin after ignoring O(a_ij^2) terms.
  • Conclusion: With the specified gin and gout, GAMP is heuristically a quadratic approximation of max-sum loopy BP for MAP estimation.The derivation is an approximation rather than a rigorous proof of equivalence.

APPENDIX D SUM-PRODUCT GAMP

This appendix extends the approximation analysis to sum-product loopy BP for MMSE estimation. Gaussian approximations to the messages yield GAMP input and output functions for conditional-mean estimation.

  • Sum-product BP: Sum-product BP represents messages as log-likelihood estimates for x_j conditioned on q, y, and A.Its output-node update differs from max-sum BP, while its input-node update remains identical.
  • Estimation: The final sum-product message defines a conditional distribution for x_j from which its conditional mean can be computed.The estimate is therefore based on MMSE-style posterior averaging rather than maximization.
  • Gaussian approximation: GAMP heuristically approximates the sum-product updates using Gaussian message representations and second-order expansions.The derivation follows the max-sum approximation while accounting for the altered output update.
  • Output approximation: For large n, the Central Limit Theorem motivates approximating the conditional distribution of z_i as Gaussian with mean b_p and variance τ_p.This Gaussian form is then used to approximate the reverse message.
  • GAMP correspondence: The resulting gout definition agrees with the sum-product expressions, while the gin update matches the conditional distribution of X given the effective input.The appendix concludes that the remaining equivalence follows as in the max-sum derivation.

APPENDIX E PROOF OF (78)

The proof establishes D(Kp)=0 when Kp has the specified form and gout(·) is given by (36). It does so by rewriting D(Kp), applying Gaussian identities, and simplifying the resulting derivative expression.

  • For Kp of the form (73), direct substitution and differentiation of the logarithm show that D(Kp)=0, proving (78).
  • D(Kp) is rewritten using a two-dimensional random vector of partial derivatives with respect to z and bP.
  • Stein’s Lemma and the covariance relation are used to transform the expression for D(Kp).

APPENDIX F PROOF SKETCH FOR CLAIM 2

The proof sketch extends the scalar Bayati–Montanari argument to vector-valued iterations. Its key ingredients are Gaussian conditioning, induction over iterations, and a matrix form of Stein’s Lemma.

  • The vector-valued result requires only minor modifications to the previously established scalar Bayati–Montanari proof.
  • The proof organizes prior iterates into matrices such as b(t) and V(t), then decomposes new vectors into parallel and orthogonal components.
  • Lemma 3 states conditional-distribution, empirical-function, limit, and derivative properties for all iteration indices under the stated assumptions.
  • The limiting expectations involve Gaussian vectors and independent variables whose marginal distributions are specified by the state-evolution limits.
  • The central conditioning argument evaluates the distribution of A under linear constraints as a deterministic offset plus a projected Gaussian.
  • A matrix version of Stein’s Lemma supplies the remaining non-trivial extension and supports the derivative statements in Lemma 3.
Loading 1010.5141v2…