PaperlayerView exact revision on arXiv

Source-linked AI summary

Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior

Subhojit Som, Philip Schniter

arXiv:1108.2632v1cs.CV

TL;DR

Compressive imaging must recover sparse natural images while exploiting persistence across scales in their wavelet coefficients. The paper combines HMT-based loopy belief propagation with a turbo schedule and AMP, and experiments report state-of-the-art reconstruction with substantially lower complexity. On 591 natural images, the method outperformed variational Bayes while halving its runtime.

  • Problem

    Compressive imaging requires estimating images from noisy undersampled measurements, while natural-image wavelet coefficients also exhibit persistence across scales that existing methods model imperfectly.

  • Method

    The method uses conditionally Gaussian HMT coefficient models and turbo LBP, alternating HMT sum-product inference with AMP for the compressive-measurement structure.

  • Results

    On 591 natural images, the proposed method outperformed variational Bayes while halving its runtime.

  • Takeaways & Limitations

    Turbo HMT inference combines improved reconstruction NMSE with lower complexity than the tested competing approaches.

Abstract

from arXiv · show

We propose a novel algorithm for compressive imaging that exploits both the sparsity and persistence across scales found in the 2D wavelet transform coefficients of natural images. Like other recent works, we model wavelet structure using a hidden Markov tree (HMT) but, unlike other works, ours is based on loopy belief propagation (LBP). For LBP, we adopt a recently proposed "turbo" message passing schedule that alternates between exploitation of HMT structure and exploitation of compressive-measurement structure. For the latter, we leverage Donoho, Maleki, and Montanari's recently proposed approximate message passing (AMP) algorithm. Experiments with a large image database suggest that, relative to existing schemes, our turbo LBP approach yields state-of-the-art reconstruction performance with substantial reduction in complexity.

I. INTRODUCTION

The paper addresses compressive imaging by modeling both wavelet sparsity and persistence across scales with an HMT-based Bayesian approach. It proposes turbo LBP, alternating HMT inference with AMP, and reports strong reconstruction performance with lower complexity.

  • Problem: Compressive imaging estimates an N-dimensional image from M ≤ N noisy linear observations using a sparse wavelet representation.Recovery is possible when the number of large coefficients is sufficiently small and the measurement matrix is incoherent with the wavelet basis.
  • Signal structure: Persistence across scales organizes 2D wavelet coefficients into quad-trees, where small parents tend to have small children and large parents tend to have some large children.This structure motivates HMT-based models for natural-image coefficients.
  • Related work: Prior approaches exploit PAS through deterministic model-based methods, iteratively re-weighted ℓ1 with Viterbi inference, MCMC, or other Bayesian HMT techniques.The paper positions its method within existing PAS-aware compressive-imaging approaches.
  • Model: The proposed method uses conditionally Gaussian wavelet coefficients whose variances depend on hidden Markov-tree states, with BG and two-state GM coefficient models.Statistical parameters are treated hierarchically as random variables with hyperpriors and learned from data.
  • Algorithm: Turbo LBP alternates standard sum-product inference over HMT structure with AMP-based inference over compressive observations.AMP provides low implementational complexity, including one forward and one inverse fast-wavelet transform per iteration.

III. IMAGE RECONSTRUCTION

The reconstruction formulation targets the posterior distribution of wavelet coefficients given compressive observations. The likelihood factors follow from the additive white Gaussian noise model and the transformed measurement matrix.

  • Posterior inference: The reconstruction objective is to infer wavelet coefficients θ by computing or approximating their posterior pdf p(θ | y).Exact posterior computation is introduced as the ideal target for image reconstruction.
  • Likelihood model: Under the white Gaussian noise model, each observation likelihood factor is Gaussian with mean determined by the corresponding row of A = ΦΨ.The matrix A combines the measurement matrix and wavelet basis.

A. Loopy Belief Propagation

LBP approximates coefficient and hidden-state marginals on the signal-model factor graph. The turbo schedule separates HMT and observation structure, then exchanges beliefs between the two subgraphs.

  • LBP: Exact posterior inference is computationally prohibitive, so LBP approximates the marginal posteriors of coefficients θn and hidden states sn.Messages are passed on the factor graph whose round nodes represent variables and square nodes represent factors.
  • Message passing: In sum-product LBP, variable-node messages multiply incoming messages from other edges, while function-node messages marginalize products of constraints and incoming messages.Messages can be interpreted as local beliefs about variables.
  • Turbo schedule: The turbo schedule splits the factor graph into two decoupled subgraphs and alternates belief propagation between them.Likelihoods produced by one subgraph serve as priors for subsequent inference in the other.

B. Message Scheduling: The Turbo Approach

The turbo schedule alternates belief propagation between compressive-measurement structure and HMT structure, passing likelihoods from one subgraph as priors to the other until convergence or a preset iteration limit.

  • B. Message Scheduling: The Turbo Approach: The factor graph is split into two decoupled subgraphs, and belief propagation alternates between them using exchanged likelihoods as updated priors.This separates soft support-recovery from soft support-decoding.
  • B. Message Scheduling: The Turbo Approach: At t = 1, the left subgraph starts from prior activity probabilities, then produces likelihood messages for HMT inference on the right subgraph.The resulting HMT messages become priors for the next left-subgraph iteration.
  • B. Message Scheduling: The Turbo Approach: Because the HMT subgraph is a tree, one forward-backward sum-product pass suffices before messages are returned to the measurement subgraph.This avoids iterative loopy updates inside the HMT component.
  • B. Message Scheduling: The Turbo Approach: Turbo iterations continue until the likelihoods converge or the maximum allowed number of iterations is reached.The likelihood messages are interpreted as extrinsic information from the corresponding decoder.

C. Soft Support-Recovery via AMP

Soft support-recovery applies AMP-style approximations to the measurement portion of the LBP factor graph, reducing per-iteration updates while accommodating independent non-identical Bernoulli-Gaussian priors.

  • C. Soft Support-Recovery via AMP: SSR fixes the HMT-derived activity priors during its inner LBP iterations and updates coefficient beliefs under those priors.The fixed prior for coefficient θn is parameterized by λn ≜ hn(sn = 1).
  • C. Soft Support-Recovery via AMP: The SSR subgraph matches the factor-graph region used to derive AMP, which the paper extends from generic i.i.d. priors to independent non-identical Bernoulli-Gaussian priors.The Bernoulli-Gaussian case is detailed explicitly.
  • C. Soft Support-Recovery via AMP: Non-Gaussian coefficient-to-measurement messages complicate exact sum-product calculations, so large-N central-limit arguments justify representing them by means and variances.This Gaussian approximation enables tractable message updates.
  • C. Soft Support-Recovery via AMP: SSR computes posterior MMSE estimates and variances for coefficients, while the posterior on each support state yields a corresponding log-likelihood ratio.These quantities provide the coefficient and support information passed through the turbo procedure.
  • C. Soft Support-Recovery via AMP: O(MN) updates are reduced to O(N) variables per LBP iteration by approximating differences among outgoing means and variances at measurement and coefficient nodes.The reduction addresses the impracticality of updating MN variables when M and N are large.
  • C. Soft Support-Recovery via AMP: AMP is initialized from scratch in the first turbo iteration and from the previous iteration’s final values thereafter, with stopping thresholds of 10^-5 and maximum limits of 10 iterations.The final coefficient mean vector is output as the signal estimate.

D. Learning the Statistical Parameters

The method learns wavelet-scale precisions, noise variance, and HMT transition probabilities from SSR outputs rather than from the unobserved true coefficients and support states.

  • D. Learning the Statistical Parameters: For active coefficients at each wavelet level, the prior precision has a Gamma posterior when the true coefficient values are available.The posterior shape and rate incorporate the number of active coefficients and their squared values.
  • D. Learning the Statistical Parameters: In practice, the algorithm updates level precisions using surrogates constructed from SSR outputs because the true coefficients and active-support sets are unavailable.These learned precisions are then used to set coefficient variances for the next SSR iteration.
  • D. Learning the Statistical Parameters: The noise variance is learned similarly from the residual estimated by SSR.This ties the noise update to the measurement-domain reconstruction residual.
  • D. Learning the Statistical Parameters: For HMT transitions, the probability that an active parent has an active child has a Beta posterior based on active-parent and active-child counts.The conjugate Bernoulli likelihood gives the stated Beta form.
  • D. Learning the Statistical Parameters: Because the true support counts are unavailable, transition-probability updates use SSR-derived approximations to active states and their parent-child counts.The updated expected transition probabilities are used in the next SSR iteration.

E. The Two-State Gaussian-Mixture Model

The paper considers both Bernoulli-Gaussian and two-state Gaussian-mixture coefficient models, retaining the AMP procedure while changing the model-specific functions and support likelihoods.

  • E. The Two-State Gaussian-Mixture Model: Two coefficient models are considered: Bernoulli-Gaussian and two-state Gaussian mixture.The exposition treats the Bernoulli-Gaussian model first and introduces the Gaussian-mixture case later.
  • E. The Two-State Gaussian-Mixture Model: AMP uses the same procedural steps for both priors, but the functions Fn, Gn, F′n, and τn are model-specific.The Bernoulli-Gaussian functions are given separately from the Gaussian-mixture functions.
  • E. The Two-State Gaussian-Mixture Model: The extrinsic support log-likelihood ratio has one expression for the Bernoulli-Gaussian case and a different expression for the Gaussian-mixture case.The distinction changes the support information supplied within the turbo procedure.

A. Setup

Experiments use 128 × 128 grayscale images with four-level Haar wavelets, Gaussian measurements, and comparisons against tree-sparse and simple-sparse reconstruction methods.

  • A. Setup: The evaluation uses 128 × 128 grayscale images, a J = 4-level 2D Haar decomposition, and i.i.d. Gaussian measurement matrices.The wavelet representation yields 64 approximation coefficients and 192 individual Markov trees.
  • A. Setup: Comparisons include ModelCS, HMT+IRWL1, MCMC, VB, CoSaMP, SPGL1, and Bernoulli-Gaussian AMP.The baselines span tree-sparse and simple-sparse reconstruction approaches.
  • A. Setup: The proposed Turbo-BG and Turbo-GM schemes use hierarchical Bayesian hyperparameter learning with wavelet-scale-specific priors.Their hyperparameters encode scale-dependent coefficient statistics and HMT activity structure.

B. Results

Across natural-image experiments, the Turbo schemes achieve the strongest reconstruction quality while substantially reducing runtime relative to Bayesian competitors. Their advantage is also observed across measurement counts, although CoSaMP remains faster under the reported single-reconstruction timing.

  • B. Results: The proposed Turbo algorithms achieve the best reconstruction NMSE across 591 images, while CoSaMP is fastest in the reported timings.CoSaMP runtimes represent a single reconstruction, despite potentially requiring multiple tuning-parameter trials.
  • B. Results: MCMC is 0.39dB worse than Turbo-BG and 0.65dB worse than Turbo-GM, while running 15 times slower than the Turbo schemes.VB is 1.5 dB and 1.7dB worse than Turbo-BG and Turbo-GM, respectively, and remains twice as slow.
  • B. Results: Combining AMP with HMT structure improves NMSE while reducing runtime relative to non-turbo alternatives.The paper attributes the complexity reduction to faster AMP and parameter-learning convergence plus negligible HMT-step cost; at M = 5000, these portions take approximately 6 sec and 0.02 sec.
  • B. Results: Turbo-GM provides uniformly best NMSE across M = 2500, 5000, 7500, 10000, and 12500 for Type 1 images.At lower measurement counts, Turbo-GM, Turbo-CS, and MCMC show little NMSE difference; at higher counts, Turbo-GM and Turbo-CS outperform MCMC and VB.

V. CONCLUSION

The paper presents turbo loopy belief propagation with AMP for HMT-based compressive imaging and reports state-of-the-art reconstruction with substantially lower runtime than variational Bayes.

  • V. CONCLUSION: The proposed HMT-based loopy-belief-propagation approach leverages a turbo schedule and AMP, outperforming variational Bayes on 591 natural images while halving its runtime.The conclusion summarizes the method and its principal empirical comparison.
Loading 1108.2632v1…