Lower bounds for sparse recovery

We consider the following k-sparse recovery problem: design an m x n matrix A, such that for any signal x, given Ax we can efficiently recover ^x satisfying x|| ^x||1 [less than or equal to] C min[subscript k]-sparse x'||x - x'||1. It is known that there exist matrices A with this prop...

Full description

Bibliographic Details
Main Authors: Indyk, Piotr, Do Ba, Khanh, Price, Eric C., Woodruff, David P.
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:en_US
Published: Society for Industrial and Applied Mathematics 2011
Online Access:http://hdl.handle.net/1721.1/62797
https://orcid.org/0000-0002-7983-9524