Bayesian compressive sensing via belief propagation

Dror Baron, Shriram Sarvotham, Richard G. Baraniuk

Research output: Contribution to journalArticlepeer-review

348 Scopus citations


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

Original languageEnglish (US)
Article number5169989
Pages (from-to)269-280
Number of pages12
JournalIEEE Transactions on Signal Processing
Issue number1
StatePublished - Jan 2010


  • Bayesian inference
  • Belief propagation
  • Compressive sensing
  • Fast algorithms
  • Sparse matrices

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Signal Processing


Dive into the research topics of 'Bayesian compressive sensing via belief propagation'. Together they form a unique fingerprint.

Cite this