A game theoretic approach to expander-based compressive sensing

Sina Jafarpour, Volkan Cevher, Robert E. Schapire

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

5 Scopus citations

Abstract

We consider the following expander-based compressive sensing (e-CS) problem: Given Φ ∈ ℝM×N (M < N), which is the adjacency matrix of an expander graph, and a vector y ∈ ℝM, we seek to find a vector x* with at most k-nonzero entries such that x* = argmin ∥x∥o≤κ∥y-Φ∥1, whenever it exists (k≪N). Such problems are not only nonsmooth, barring naive convexified sparse recovery approaches, but also are NP-Hard in general. To handle the non-smoothness, we provide a saddle-point reformulation of the e-CS problem, and propose a novel approximation scheme, called the game-theoretic approximate matching estimator (GAME) algorithm. We then show that the restricted isometry property of expander matrices in the ℓ1-norm circumvents the intractability of e-CS in the worst case. GAME therefore finds a sparse approximation x to optimal solution such that ∥x*- x̂∥ = O (∥y - Φx ∥x*1). We also propose a convex optimization approach to e-CS based on Nesterov smoothing, and discuss its (dis)advantages.

Original languageEnglish (US)
Title of host publication2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Pages464-468
Number of pages5
DOIs
StatePublished - 2011
Event2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation
Duration: Jul 31 2011Aug 5 2011

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8104

Other

Other2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
CountryRussian Federation
CitySt. Petersburg
Period7/31/118/5/11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A game theoretic approach to expander-based compressive sensing'. Together they form a unique fingerprint.

  • Cite this

    Jafarpour, S., Cevher, V., & Schapire, R. E. (2011). A game theoretic approach to expander-based compressive sensing. In 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 (pp. 464-468). [6034169] (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2011.6034169