TY - GEN

T1 - A game theoretic approach to expander-based compressive sensing

AU - Jafarpour, Sina

AU - Cevher, Volkan

AU - Schapire, Robert E.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=80054829552&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80054829552&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2011.6034169

DO - 10.1109/ISIT.2011.6034169

M3 - Conference contribution

AN - SCOPUS:80054829552

SN - 9781457705953

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 464

EP - 468

BT - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011

T2 - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011

Y2 - 31 July 2011 through 5 August 2011

ER -