PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayesian Compressive Sensing via Belief Propagation

Dror Baron, Shriram Sarvotham, Richard G. Baraniuk

arXiv:0812.4627v2cs.IT

TL;DR

High-dimensional sparse signals can be recovered from few measurements, but conventional CS decoding may be computationally costly. The paper introduces CS-BP, combining sparse encoding matrices with belief propagation for approximate Bayesian inference. It reports O(Klog(N)) measurements and O(Nlog^2(N)) computation, while noting scope limitations for arbitrary bases and nonideal BP graphs.

  • Problem

    Conventional CS methods can be computationally expensive, while available signal statistics could support more precise estimation or fewer measurements through Bayesian inference.

  • Method

    CS-BP uses sparse CS-LDPC-like encoding matrices and belief propagation on a sparse bipartite graphical model to perform approximate Bayesian decoding.

  • Results

    CS-BP requires 20–30% fewer measurements than LP and GPSR for the same MMSE decoding error, with greater advantage over IHT and CoSaMP.

  • Takeaways & Limitations

    CS-BP provides a flexible Bayesian CS framework that supports approximately sparse signals, other sparsifying bases, modified signal models, and measurement noise.

  • Takeaways & Limitations

    CS-BP is not universal: arbitrary sparsifying bases require modifying the encoding and decoding methods, and BP can suffer from loops and message-encoding errors.

Abstract

from arXiv · show

Compressive sensing (CS) is an emerging field based on the revelation that a small collection of linear projections of a sparse signal contains enough information for stable, sub-Nyquist signal acquisition. When a statistical characterization of the signal is available, Bayesian inference can complement conventional CS methods based on linear programming or greedy algorithms. We perform approximate Bayesian inference using belief propagation (BP) decoding, which represents the CS encoding matrix as a graphical model. Fast computation is obtained by reducing the size of the graphical model with sparse encoding matrices. To decode a length-N signal containing K large coefficients, our CS-BP decoding algorithm uses O(Klog(N)) measurements and O(Nlog^2(N)) computation. Finally, although we focus on a two-state mixture Gaussian model, CS-BP is easily adapted to other signal models.

1 Introduction

Compressive sensing recovers high-dimensional signals from few linear projections by exploiting sparsity, but conventional optimization-based decoding can be computationally expensive. CS-BP combines sparse encoding with Bayesian belief-propagation decoding to accelerate acquisition and inference.

  • Motivation: A few large coefficients often contain most signal information, allowing sparse signals to be captured through a small number of random linear projections.Traditional sensing acquires the full data before discarding most coefficients.
  • Compressive sensing setup: CS represents x = Ψθ with sparse coefficients θ and acquires M ≪ N measurements through y = Φx.The basis Ψ can be arbitrary, while Φ maps the signal to linear projections.
  • Decoding challenge: ℓ1 decoding requires M = O(K log(N/K)) projections but can require cubic computation, while solving the exact ℓ0 problem is NP-complete.These costs motivate faster decoding methods for high-dimensional applications.
  • Prior approaches: Greedy methods such as OMP, CoSaMP, IHT, and Subspace Pursuit seek faster alternatives to optimization-based decoders while retaining comparable guarantees.Their shared strategy is iterative selection or thresholding based on the measurement structure.
  • CS-BP contribution: CS-BP develops a sparse encoder matrix and belief-propagation decoder for Bayesian CS, emphasizing a two-state mixture Gaussian prior while allowing model variations.Sparse matrices enable sums and differences over small coefficient subsets, and BP operates on the resulting sparse bipartite graph.

2 Mixture Gaussian signal model

The paper models approximately sparse coefficients with a two-state mixture Gaussian prior. Each coefficient’s latent state distinguishes large from small magnitudes, with the model controlled by sparsity and Gaussian variance parameters.

  • Latent states: Each coefficient is assigned a binary state Q(i), with large and small magnitudes modeled by zero-mean Gaussians of high and low variance, respectively.Q(i) = 1 denotes the high-variance state and Q(i) = 0 the low-variance state.
  • Sparsity prior: The states are iid Bernoulli variables with Pr(Q(i) = 1) = S and Pr(Q(i) = 0) = 1 − S, where S = K/N.This prior targets approximately K large coefficients among N signal entries.
  • Mixture model: The resulting coefficient distribution is characterized by the sparsity rate S and the two Gaussian variances σ0^2 and σ1^2.The overall mixture combines the state-conditional Gaussian distributions.
  • Model scope: Two-state mixture Gaussian models are simple and effective for modeling real-world signals and have been used in image processing and inference.The paper notes that richer models could use more states or nonzero means, but leaves those extensions for future work.

3 Sparse encoding

CS-BP uses sparse LDPC-like encoding matrices whose graph structure accelerates encoding while retaining enough information for Bayesian decoding. The section establishes measurement, accuracy, and computational guarantees under a two-state mixture Gaussian model.

  • Sparse encoding: Sparse CS-LDPC matrices use entries in {−1, 1}, so each measurement requires only sums and differences of a small subset of coefficients.Their row and column weights are designed according to the signal, measurement, and decoding models.
  • Information content: A sparse encoding matrix can retain enough information for accurate decoding despite potentially higher coherence with the sparsifying basis than a dense matrix.Theorem 1 provides the formal condition under which the measurements remain sufficient.
  • Scope: The method assumes sparsity in the canonical basis, while extensions to signals sparse in another basis may require more complicated encoding matrices.The paper emphasizes that such extensions can be possible in practical situations.
  • Guarantees: M = O(K log(N)) measurements are sufficient under the theorem’s sparsity-rate and matrix-weight conditions.The theorem considers a two-state mixture Gaussian signal and a CS-LDPC matrix with specified row weight.
  • Guarantees: ∥x − bx∥∞ < µσ1 holds with probability 1 − 2N^−γ for the theorem’s two-state mixture Gaussian and CS-LDPC setting.The guarantee is an ℓ∞ decoding bound under the stated matrix and signal assumptions.
  • Computational cost: O(N log(N)) encoding computation is required, compared with O(MN) = O(KN log(N)) for dense Gaussian encoding.Each measurement uses O(L) additions and subtractions under the proposed rules of thumb.

4 CS-BP decoding of approximately sparse signals

CS-BP formulates approximately sparse signal recovery as Bayesian inference on a sparse factor graph and approximates posterior marginals through belief propagation. Sparse graphs reduce computational cost, while message representations introduce flexibility and convergence trade-offs.

  • Bayesian formulation: CS-BP estimates an approximately sparse signal by selecting, among solutions to y = Φx, the one that best matches the prior model.The posterior estimate is sought in the underdetermined solution hyperplane.
  • Message passing: BP passes messages between variable and constraint nodes to approximate marginal distributions conditioned on observed measurements.Variable-node updates multiply incoming beliefs, while constraint-node updates apply constraints and marginalize through convolution.
  • Message passing: Marginal distributions support MAP, MMSE, error-bar, and other statistical characterizations of coefficient estimates.The coefficient and state marginals are conditioned on the observed measurements.
  • Convergence: CS-BP is not guaranteed to converge because its factor graph has loops and message encoding introduces errors, although damping and sparse graphs can reduce these problems.The paper reports promising numerical performance despite this lack of guarantee.
  • Complexity: O(N log^2(N)) computation is required to decode a length-N signal containing K large coefficients, using O(K log(N)) measurements.The complexity follows from sparse message processing and convolution operations over the graph.
  • Message representations: Message encoding with pdf samples offers prior flexibility but requires more memory and can introduce quantization errors that impair precision and convergence.Mixture Gaussian messages use shorter representations but are harder to adapt to other priors.
  • Properties: Progressive decoding, state-only estimation, and noise convolution provide additional decoding properties within the CS-BP framework.More measurements improve posterior precision, state-only estimates can reduce measurements, and noisy measurements can be incorporated through convolution.

5 Numerical results

The experiments evaluate CS-BP across matrix designs, competing decoders, signal lengths, measurement noise, and model mismatch. CS-BP can reduce measurements, but its runtime and robustness depend on setting and implementation choices.

  • Matrix design: An optimal row weight Lopt ≈2/S = 20 minimizes required measurements, while larger values yield marginal gains and can cause CS-BP divergence.Small row weights may miss large coefficients; values above Lopt diverge even with damping.
  • Decoder comparison: CS-BP requires 20–30% fewer measurements than LP and GPSR for the same MMSE error, with a larger advantage over IHT and CoSaMP.Its advantage over LP and GPSR becomes less pronounced as M increases.
  • Runtime: CS-BP runtime scales somewhat better than IHT and GPSR, although it remains slower than them at N = 10000 because each iteration performs FFT computations.LP scales more poorly and was not simulated for N > 3000.
  • Measurement noise: Measurement noise increases decoding error, but when σ2_Z ≪18, noise has little impact and CS-BP degrades gracefully.The average measurement picks up a Gaussian signal term with variance 18 in the stated setting.
  • Model mismatch: As mixture components increase, CS-BP MMSE increases; GPSR degrades more gracefully, while IHT also degrades significantly under model mismatch.For C = 3, the effective sparsity rate doubles from S to 2S, so more measurements are expected.

6 Variations and enhancements

The paper describes extensions of CS-BP beyond the canonical basis and iid priors, plus feedback and irregular matrix designs. These modifications target broader signal models, dependencies, lost measurements, and fewer required measurements.

  • Supporting arbitrary sparsifying basis Ψ: CS-BP supports signals sparse in an arbitrary basis by encoding with ΦΨT, decoding coefficients with BP, and transforming them back via Ψ.The canonical case assumes Ψ = I.
  • Exploiting statistical dependencies: Modeling dependencies among coefficients can enable decoding from fewer measurements by assigning different distributions to different coefficients.The paper gives parent–child correlations in wavelet representations as an example.
  • Feedback: Decoder feedback can stop the measurement stream once marginal distributions indicate that sufficient information for decoding has been received.This is intended for applications where measurements may be lost during transmission.
  • Irregular CS-LDPC matrices: Irregular CS-LDPC matrices are expected to further reduce the number of measurements required.The analogy is to irregular LDPC matrices in channel coding, where a small number of high-weight rows or columns can reduce block error rates with modest computation.

7 Discussion

The paper combines sparse encoding with belief-propagation decoding to provide fast Bayesian compressed sensing, with probabilistic guarantees for the mixture-Gaussian model. CS-BP is flexible but requires basis-specific modifications and depends on sparse CS-LDPC matrices.

  • Contributions: CS-BP combines a sparse encoding matrix with belief propagation to accelerate Bayesian compressed-sensing encoding and decoding.The proof combines probabilistic bounds on signal norms with a prior theorem on sparse random matrices.
  • Scope and flexibility: The framework can address approximately sparse signals, modified signal models, other sparsifying bases, and measurement noise.Applying it to arbitrary bases requires modifying the encoding matrix and decoding method, using multiplication by Ψ or ΨT.
  • Computational performance: O(N log^2(N)) computation makes CS-BP faster than previous Bayesian compressed-sensing methods.The comparison is explicitly made against prior Bayesian approaches.
  • Scope and limitations: CS-BP relies on sparse CS-LDPC matrices, and its applicability to different applications remains a topic for future research.The paper compares its graph structure with sparse parity-check matrices used in LDPC codes.
  • Theoretical guarantees: With probability at least 1 − 2N^-γ, the decoding approximations satisfy the stated theorem guarantee when the required norm bounds hold.The proof combines the probability of the ℓ2 and ℓ∞ bounds with the decoding probability.
Loading 0812.4627v2…