PaperlayerView exact revision on arXiv

Source-linked AI summary

Message Passing Algorithms for Compressed Sensing: I. Motivation and Construction

David L. Donoho, Arian Maleki, Andrea Montanari

arXiv:0911.4219v1cs.IT

TL;DR

The paper studies how to reconstruct sparse signals from underdetermined linear measurements while retaining both computational simplicity and reconstruction power. It derives approximate message passing from belief propagation, extends the framework to several settings, and characterizes its large-system and large-β simplifications. The paper's central outcome is a low-complexity AMP formulation motivated by these approximations.

  • Problem

    Sparse recovery from underdetermined measurements requires methods that address the complexity of basis-pursuit optimization while retaining its reconstruction power.

  • Method

    The paper derives AMP by applying sum-product belief propagation to a β-parameterized graphical model, then using large-system and large-β approximations.

  • Results

    The derivation yields AMP as a low-complexity algorithm combining iterative thresholding complexity with basis-pursuit reconstruction power.

  • Takeaways & Limitations

    AMP provides a message-passing framework extended to basis-pursuit denoising, Lasso, and Bayesian reconstruction settings.

Abstract

from arXiv · show

In a recent paper, the authors proposed a new class of low-complexity iterative thresholding algorithms for reconstructing sparse signals from a small set of linear measurements \cite{DMM}. The new algorithms are broadly referred to as AMP, for approximate message passing. This is the first of two conference papers describing the derivation of these algorithms, connection with the related literature, extensions of the original framework, and new empirical evidence. In particular, the present paper outlines the derivation of AMP from standard sum-product belief propagation, and its extension in several directions. We also discuss relations with formal calculations based on statistical mechanics methods.

I. INTRODUCTION

The paper addresses sparse-signal recovery from underdetermined linear measurements and motivates AMP as a low-complexity alternative combining iterative thresholding with basis-pursuit reconstruction power.

  • I. INTRODUCTION: Sparse signals can be recovered exactly or approximately from fewer linear measurements when their underlying structure is suitable.The measurements are y = As_o with n < N, so the system is underdetermined.
  • I. INTRODUCTION: Basis pursuit uses ℓ1 minimization to solve underdetermined compressed-sensing systems.Its solution can be obtained with generic linear-programming algorithms.
  • I. INTRODUCTION: Standard LP solvers are too complex for large-scale applications, while iterative thresholding has lower complexity but a worse sparsity-undersampling tradeoff.The cited applications include magnetic resonance imaging and seismic data analysis.
  • I. INTRODUCTION: AMP is presented as combining the low complexity of iterative thresholding with the reconstruction power of basis pursuit.AMP stands for approximate message passing.
  • I. INTRODUCTION: The paper derives AMP from sum-product belief propagation and extends it to basis-pursuit denoising, Lasso, and Bayesian settings.It also discusses connections with formal statistical-mechanics calculations.
  • I. INTRODUCTION: Proofs are omitted because of space limitations and are available in a longer version.

III. AMP FOR THE BASIS PURSUIT

For basis pursuit, AMP is derived by embedding the optimization problem in a β-parameterized graphical model, approximating belief-propagation messages in the large-system limit, and simplifying their parameter updates.

  • III. AMP FOR THE BASIS PURSUIT: The derivation constructs a joint distribution over signal variables and applies sum-product belief propagation.The distribution is parameterized by β and associated with the basis-pursuit problem.
  • III. AMP FOR THE BASIS PURSUIT: As β approaches infinity, the distribution concentrates around the solution of the ℓ1 minimization problem.Access to the distribution's marginals would therefore solve the optimization problem.
  • III. AMP FOR THE BASIS PURSUIT: The factor graph is complete bipartite, with N variable nodes, n factor nodes, and probability-measure messages on every edge.This yields messages indexed by variable-to-factor and factor-to-variable edges.
  • III. AMP FOR THE BASIS PURSUIT: In the large-system limit, factor-to-variable messages are approximately Gaussian, while variable-to-factor messages are approximated by Gaussian-Laplace products.The Gaussian messages are characterized by scalar parameters such as means and variances.
  • III. AMP FOR THE BASIS PURSUIT: The approximation assumes concentration and edge-independence properties for the messages in the large-system regime.The stated bounds and approximations are formulated uniformly in system size or edge choice where specified.
  • III. AMP FOR THE BASIS PURSUIT: The message parameters are reduced to means and variances whose update rules are computed from the approximating message densities.The derivation introduces density families and tracks their parameters across iterations.

C. Large β limit

The large-β analysis turns the belief-propagation scalar functions into soft-thresholding and derivative-based expressions, yielding an equivalent large-β message-passing form.

  • C. Large β limit: The soft-thresholding function is η(x; b) = sign(x)(|x| − b)+.It provides the limiting estimator in the β → ∞ analysis.
  • C. Large β limit: As β approaches infinity, F_β(x; b) converges to η(x; b), the soft-thresholding function.The limiting integral is dominated by the exponent's maximum at the thresholded value.
  • C. Large β limit: For bounded x and b, βG_β(x; b) converges to bη′(x; b).When the thresholded solution is zero, the variance is of smaller order and becomes negligible.
  • C. Large β limit: These limiting identities, together with earlier lemmas, yield an equivalent message-passing algorithm for large β.

D. From message passing to AMP

The paper simplifies the edge-wise message-passing updates into AMP by exploiting large-system message approximations, while noting that the derivation controls only a single iteration step.

  • D. From message passing to AMP: Tracking the message-passing algorithm directly requires updating 2nN messages per iteration, motivating further simplification.The simplification is based on approximating messages with lower-dimensional quantities.
  • D. From message passing to AMP: The analysis assumes edge-uniform asymptotic approximations and studies general message-passing algorithms with differentiable nonlinearities and bounded derivatives.Lipschitz-continuous nonlinearities are also stated to preserve the result in the relevant case.
  • D. From message passing to AMP: Under these assumptions, the message variables satisfy simplified equations whose error terms vanish in the large-system limit.The vanishing terms are denoted o_N(1).
  • D. From message passing to AMP: The resulting algorithm is expressed in vector notation using averages of vector quantities.
  • D. From message passing to AMP: The derivation also supplies a recursion for the variance parameter τ̂.

E. Comments

The derivation yields a parameter-free AMP threshold recursion, but its long-term iterative validity remains mathematically unproven.

  • The derived AMP algorithm updates its threshold level recursively, rather than requiring an externally optimized threshold sequence.The authors expect the recursive and optimized viewpoints to coincide in the large-system limit, while allowing general threshold sequences may be advantageous.
  • The simplification of sum-product updates is justified only in the large-system and large-β limits.
  • The analysis establishes control for a single iterative step, not accurate message tracking across finitely many iterations.Accumulated approximation errors could in principle become large, although the authors do not expect this.

IV. AMP FOR BPDN/LASSO

The paper extends the AMP derivation from basis pursuit to BPDN/Lasso, obtaining a related vector algorithm whose threshold recursion is the only stated difference.

  • BPDN/Lasso is introduced as another compressed-sensing reconstruction procedure.
  • The corresponding AMP derivation follows the same general procedure as the preceding basis-pursuit derivation, with selected differences.
  • The constructed joint distribution has a mode coinciding with the optimization solution and concentrates there as β →∞.
  • The resulting vector-form algorithm generalizes the earlier AMP equations for basis pursuit.
  • The threshold-level recursion is the only stated deviation from the algorithm in the preceding section.

V. AMP FOR RECONSTRUCTION WITH PRIOR

For known signal priors, the paper replaces soft thresholding with conditional-mean estimation and derives a Bayesian AMP algorithm using scalar message parameters.

  • Known signal distributions can provide extra information for improving recovery algorithms and serve as benchmarks for approaches without prior knowledge.
  • The Bayesian construction starts from the product prior α = α1×α2 · · ·×αN over the signal variables.
  • The posterior distribution is defined for noisy observations y = As + w, with independent Gaussian noise w.
  • Belief-propagation messages are probability measures or non-negative measurable functions, and the simplified derivation introduces scalar-parameterized measure families.
  • The functions Fi and Gi are defined as the mean and variance of the corresponding scalar measure, while also admitting conditional-expectation and conditional-variance interpretations under Gaussian noise.
  • The resulting vector AMP uses F componentwise, with its derivative and threshold level computed iteratively.

A. Comments

The prior-informed AMP variant is only marginally more complex because it replaces soft thresholding with conditional expectation, which may require numerical approximation.

  • The prior-informed AMP algorithm is marginally more complex than the preceding algorithms.
  • Its main change is replacing the soft-thresholding function η(·) with the conditional expectation F(·).
  • Because F generally lacks a closed form, accurate and easily evaluated approximations can be constructed.

VI. RELATED WORK

Earlier message-passing approaches to compressed sensing faced impractical continuous messages, dense-graph computation, and the need for an unavailable prior. The present approach addresses these difficulties through Gaussian message approximations and a Laplace prior linked to basis pursuit and soft thresholding.

  • Computational difficulties: Standard belief propagation is computationally impractical because it uses probability-measure messages on a dense complete bipartite graph.Updating the graph requires Nn messages per iteration, with each update depending on N or n input messages.
  • Gaussian approximation: High graph density makes factor-to-variable messages approximately Gaussian, so tracking their means and variances reduces the message representation.Because messages departing from the same node are similar, tracking only the means is sufficient in the described approximation.
  • Prior specification: Belief propagation also requires a prior on the signal, but most compressed-sensing applications lack a suitable prior.The paper addresses this difficulty by using a Laplace prior.
  • Prior specification: As β →∞, the Laplace-prior formulation concentrates at the basis-pursuit solution and is connected to the soft-threshold nonlinearity η(x; θ).The soft-threshold rule is described as step-by-step optimal in a minimax sense.

B. Historical background and statistical physics

Message passing in compressed sensing connects to statistical-physics approximations and to density evolution from coding theory. In dense graphs, state evolution replaces the locally tree-like justification used for sparse graphs and links AMP behavior to replica-based fixed-point equations.

  • Statistical-physics connections: The sum-product algorithm corresponds to the Bethe-Peierls approximation, whose fixed points are stationary points of the Bethe free energy.In spin-glass theory, the same approximation is also called the replica-symmetric cavity method.
  • Statistical-physics connections: For complete-graph spin glasses, Bethe-Peierls equations reduce to TAP equations for local magnetizations.TAP adds an Onsager reaction term because naive mean field is not sufficiently accurate for the spin-glass model.
  • State evolution: Density evolution is asymptotically exact for sparse random graphs because they converge locally to trees, where density evolution is exact.This tree-based justification does not apply to the dense-graph setting considered for AMP.
  • State evolution: State evolution is the dense-graph analogue of density evolution, but its success requires mathematical ideas beyond local tree-likeness.Its fixed points describe AMP output after sufficiently many iterations, independently of n and N.
  • Replica method: State-evolution fixed-point equations coincide with those obtained from the replica-symmetric replica method.The paper places this agreement within a broader equivalence between replica and cavity methods.
  • Replica method: Compared with the replica method, state evolution is more concrete, quantitatively checkable through simulations, and closely related to efficient message passing algorithms.The supplied passage introduces these as advantages of the state-evolution formalism.
Loading 0911.4219v1…