### 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 language | English (US) |
---|---|

Title of host publication | 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 |

Pages | 464-468 |

Number of pages | 5 |

DOIs | |

State | Published - 2011 |

Event | 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation Duration: Jul 31 2011 → Aug 5 2011 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

ISSN (Print) | 2157-8104 |

### Other

Other | 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 |
---|---|

Country | Russian Federation |

City | St. Petersburg |

Period | 7/31/11 → 8/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

*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