A Game Theoretic Approach to Expander-based Compressive Sensing

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 equation 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̂ ||1 = O (||y - Φx*||1). We also propose a convex optimization approach to e-CS based on Nesterov smoothing, and discuss its (dis)advantages.


Published in:
Proceedings of the IEEE International Symposium on Information Theory, 464 - 468
Presented at:
IEEE International Symposium on Information Theory (ISIT), St. Petersburg , Russia, July 31 - August 5, 2011
Year:
2011
Publisher:
IEEE
Keywords:
Laboratories:




 Record created 2011-02-16, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)