Model-based compressive sensing

Richard G. Baraniuk, Volkan Cevher, Marco F. Duarte, Chinmay Hegde

Research output: Contribution to journalArticle

1135 Scopus citations

Abstract

Compressive sensing (CS) is an alternative to Shannon/Nyquist sampling for the acquisition of sparse or compressible signals that can be well approximated by just K≪ll N elements from an N-dimensional basis. Instead of taking periodic samples, CS measures inner products with M < N random vectors and then recovers the signal via a sparsity-seeking optimization or greedy algorithm. Standard CS dictates that robust signal recovery is possible from =O(Klog(N/K))measurements. It is possible to substantially decrease M without sacrificing robustness by leveraging more realistic signal models that go beyond simple sparsity and compressibility by including structural dependencies between the values and locations of the signal coefficients. This paper introduces a model-based CS theory that parallels the conventional theory and provides concrete guidelines on how to create model-based recovery algorithms with provable performance guarantees. A highlight is the introduction of a new class of structured compressible signals along with a new sufficient condition for robust structured compressible signal recovery that we dub the restricted amplification property, which is the natural counterpart to the restricted isometry property of conventional CS. Two examples integrate two relevant signal modelswavelet trees and block sparsityinto two state-of-the-art CS recovery algorithms and prove that they offer robust recovery from just M=O(K) measurements. Extensive numerical simulations demonstrate the validity and applicability of our new theory and algorithms.

Original languageEnglish (US)
Article number5437428
Pages (from-to)1982-2001
Number of pages20
JournalIEEE Transactions on Information Theory
Volume56
Issue number4
DOIs
StatePublished - Apr 2010

Keywords

  • Block sparsity
  • Compressive sensing
  • Signal model
  • Sparsity
  • Union of subspaces
  • Wavelet tree

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Model-based compressive sensing'. Together they form a unique fingerprint.

Cite this