Sparse recovery using sparse matrices

We consider the approximate sparse recovery problem, where the goal is to (approximately) recover a high-dimensional vector x from its lower-dimensional sketch Ax. A popular way of performing this recovery is by finding x* such that Ax=Ax*, and ||x*||_1 is minimal. It is known that this approach ``w...

Full description

Bibliographic Details
Main Authors: Berinde, Radu, Indyk, Piotr
Other Authors: Piotr Indyk
Published: 2008
Online Access:http://hdl.handle.net/1721.1/40089