Computing performance guarantees for compressed sensing

Kiryung Lee, Yoram Bresler

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

Abstract

There are various conditions on the CS matrix for unique and stable recovery. These include universality, or spark, and UUP. Furthermore, quantitative bounds on the stability depend on related properties of the CS matrix. The construction of good CS matrices - satisfying the various properties - is key to successful practical applications of compressive sensing. Unfortunately, verifying the satisfiability of any of these properties for a given CS matrix involves infeasible combinatorial search. Our methods use l 1 and semidefinite relaxation into a convex problem. Given a set of candidate CS matrices, our approach provides tools for the selection of good CS matrices with verified and quantitatively favorable performance.

Original languageEnglish (US)
Title of host publication2008 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP
Pages5129-5132
Number of pages4
DOIs
StatePublished - Sep 16 2008
Event2008 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP - Las Vegas, NV, United States
Duration: Mar 31 2008Apr 4 2008

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
ISSN (Print)1520-6149

Other

Other2008 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP
CountryUnited States
CityLas Vegas, NV
Period3/31/084/4/08

    Fingerprint

Keywords

  • Basis Pursuit
  • Compressive Sampling
  • Semidefinite Programming
  • Spark
  • Uniform Uncertainty Principle

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Signal Processing
  • Acoustics and Ultrasonics

Cite this

Lee, K., & Bresler, Y. (2008). Computing performance guarantees for compressed sensing. In 2008 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP (pp. 5129-5132). [4518813] (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). https://doi.org/10.1109/ICASSP.2008.4518813