Compressive sensing meets game theory

Sina Jafarpour, Robert E. Schapire, Volkan Cevher

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

2 Scopus citations

Abstract

We introduce the Multiplicative Update Selector and Estimator (MUSE) algorithm for sparse approximation in under-determined linear regression problems. Given f = Φα* + μ, the MUSE provably and efficiently finds a k-sparse vector α such that ∥Φα - f∥ ≤ ∥μ∥ + O (1/√k), for any k-sparse vector α*, any measurement matrix Φ, and any noise vector μ. We cast the sparse approximation problem as a zero-sum game over a properly chosen new space; this reformulation provides salient computational advantages in recovery. When the measurement matrix Φ provides stable embedding to sparse vectors (the so-called restricted isometry property in compressive sensing), the MUSE also features guarantees on ∥α* - α∥2. Simulation results demonstrate the scalability and performance of the MUSE in solving sparse approximation problems based on the Dantzig Selector.

Original languageEnglish (US)
Title of host publication2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Proceedings
Pages3660-3663
Number of pages4
DOIs
StatePublished - 2011
Event36th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Prague, Czech Republic
Duration: May 22 2011May 27 2011

Publication series

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

Other

Other36th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011
CountryCzech Republic
CityPrague
Period5/22/115/27/11

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

Keywords

  • Compressed Sensing
  • Dantzig Selector
  • Game Theory
  • Multiplicative Weights Algorithm

Fingerprint Dive into the research topics of 'Compressive sensing meets game theory'. Together they form a unique fingerprint.

Cite this