Structured sublinear compressive sensing via belief propagation

Wei Dai, Olgica Milenkovic, Hoa Vin Pham

Research output: Contribution to journalArticlepeer-review


Compressive sensing (CS) is a sampling technique designed for reducing the complexity of sparse data acquisition. One of the major obstacles for practical deployment of CS techniques is the signal reconstruction time and the high storage cost of random sensing matrices. We propose a new structured compressive sensing scheme, based on codes of graphs, that allows for a joint design of structured sensing matrices and logarithmic-complexity reconstruction algorithms. The compressive sensing matrices can be shown to offer asymptotically optimal performance when used in combination with orthogonal matching pursuit (OMP) methods. For reduced-complexity greedy reconstruction schemes, we propose a new family of list-decoding belief propagation algorithms, as well as reinforced and multiple-basis belief propagation (BP) algorithms. Our simulation results indicate that reinforced BP CS schemes offer very good complexity-performance tradeoffs for very sparse signal vectors.

Original languageEnglish (US)
Pages (from-to)76-90
Number of pages15
JournalPhysical Communication
Issue number2
StatePublished - Jun 1 2012


  • Belief propagation
  • Compressive sensing
  • Low-density parity-check codes
  • Orthogonal matching pursuit
  • Restricted isometry constants
  • Sparse approximation
  • Subspace pursuit

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

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

Cite this