Rate-distortion bounds for sparse approximation

Alyson K. Fletcher, Sundeep Rangan, Vivek K. Goyal

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Sparse signal models arise commonly in audio and image processing. Recent work in the area of compressed sensing has provided estimates of the performance of certain widely-used sparse signal processing techniques such as basis pursuit and matching pursuit. However, the optimal achievable performance with sparse signal approximation remains unknown. This paper provides bounds on the ability to estimate a sparse signal in noise. Specifically, we show that there is a critical minimum signal-to-noise ratio (SNR) that is required for reliable detection of the sparsity pattern of the signal. We furthermore relate this critical SNR to the asymptotic mean squared error of the maximum likelihood estimate of a sparse signal in additive Gaussian noise. The critical SNR is a simple function of the problem dimensions.

Original languageEnglish (US)
Title of host publication2007 IEEE/SP 14th Workshop on Statistical Signal Processing, SSP 2007, Proceedings
Number of pages5
StatePublished - 2007
Event2007 IEEE/SP 14th WorkShoP on Statistical Signal Processing, SSP 2007 - Madison, WI, United States
Duration: Aug 26 2007Aug 29 2007

Publication series

NameIEEE Workshop on Statistical Signal Processing Proceedings


Other2007 IEEE/SP 14th WorkShoP on Statistical Signal Processing, SSP 2007
Country/TerritoryUnited States
CityMadison, WI


  • Basis pursuit
  • Compressed sensing
  • Estimation
  • Matching pursuit
  • Maximum likelihood
  • Unions of subspaces

ASJC Scopus subject areas

  • Signal Processing


Dive into the research topics of 'Rate-distortion bounds for sparse approximation'. Together they form a unique fingerprint.

Cite this