Bayesian Compressive Sensing Via Belief Propagation

By Dror Baron, Shriram Sarvotham, Richard Baraniuk. IEEE Transactions on Signal Processing, 2008

529 citations recorded by the source corpus.

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 asymptotically optimal 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(K log(N)) measurements and O(N log2(N)) computation. Finally, although we focus on a two-state mixture Gaussian model, CS-BP is easily adapted to other signal models.

Subfields: Computational Mechanics, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/01fdfadad51359b5b64b2a0c17379a4919f8c9e4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Compressive sensing: From theory to applications, a survey (2013, background): “Recently, proposed algorithm of belief propagation also falls in this category [43].”
Statistical physics of inference: thresholds and algorithms (2015, methodology): “A starting point in the derivation of AMP is to write the belief propagation algorithm corresponding to this graphical model, as done originally in [21].”
Fast L1-Minimization Algorithms For Robust Face Recognition (2010, unknown): “More recently, Donoho et al. [17] have shown that iterative soft-thresholding can be understood as an approximate solution to ( P 1 ) via a belief propagation framework [60].”
Sparse Recovery Using Sparse Matrices (2010, background): “In particular, there have been several schemes based on sparse matrices that work for (almost) exactly k-sparse signals [27], [29], [32], [37]–[39], [43], [44].”
Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices (2012, methodology): “Belief propagation was used for CS with sparse measurement matrices by several authors, see e.g. [22, 30, 31].”
Multilabel Classification using Bayesian Compressed Sensing (2012, methodology): “In particular, we propose a joint probabilistic model that combines compressed sensing [10, 11] with a Bayesian learning model on the projected space.”
A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed $\ell ^{0}$ Norm (2008, background): “Lemma 1: Assume a matrix n m A R   has the property that all of its n n  sub-matrices are invertible, which is called the unique representation property (URP) in [3].”
Message passing algorithms for compressed sensing: I. motivation and construction (2009, methodology): “The use of message passing algorithms for compressed sensing problems was suggested before, see for instance [6] .”
Fault Identification Via Nonparametric Belief Propagation (2009, methodology): “Variants of NBP have been used in CS [20] and low-density lattice codes (codes defined over”