A coding theory approach to noisy compressive sensing using low density frames

Mehmet Akçakaya, Jinsoo Park, Vahid Tarokh

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


We consider the compressive sensing of a sparse or compressible signal x ∈ R M. We explicitly construct a class of measurement matrices inspired by coding theory, referred to as low density frames, and develop decoding algorithms that produce an accurate estimate x̂ even in the presence of additive noise. Low density frames are sparse matrices and have small storage requirements. Our decoding algorithms can be implemented in O(Md2u) complexity, where dv is the left degree of the underlying bipartite graph. Simulation results are provided, demonstrating that our approach outperforms state-of-the-art recovery algorithms for numerous cases of interest. In particular, for Gaussian sparse signals and Gaussian noise, we are within 2-dB range of the theoretical lower bound in most cases.

Original languageEnglish (US)
Article number5970130
Pages (from-to)5369-5379
Number of pages11
JournalIEEE Transactions on Signal Processing
Issue number11
StatePublished - Nov 2011

Bibliographical note

Copyright 2011 Elsevier B.V., All rights reserved.


  • Belief propagation
  • EM algorithm
  • Gaussian scale mixtures
  • coding theory
  • compressive sensing
  • low density frames
  • sum product algorithm


Dive into the research topics of 'A coding theory approach to noisy compressive sensing using low density frames'. Together they form a unique fingerprint.

Cite this