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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Published: |
2008
|
| Online Access: | http://hdl.handle.net/1721.1/40089 |
| _version_ | 1826209780773945344 |
|---|---|
| author | Berinde, Radu Indyk, Piotr |
| author2 | Piotr Indyk |
| author_facet | Piotr Indyk Berinde, Radu Indyk, Piotr |
| author_sort | Berinde, Radu |
| collection | MIT |
| description | 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 ``works'' if A is a random *dense* matrix, chosen from a proper distribution.In this paper, we investigate this procedure for the case where A is binary and *very sparse*. We show that, both in theory and in practice, sparse matrices are essentially as ``good'' as the dense ones. At the same time, sparse binary matrices provide additional benefits, such as reduced encoding and decoding time. |
| first_indexed | 2024-09-23T14:30:00Z |
| id | mit-1721.1/40089 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T14:30:00Z |
| publishDate | 2008 |
| record_format | dspace |
| spelling | mit-1721.1/400892019-04-10T22:26:59Z Sparse recovery using sparse matrices Berinde, Radu Indyk, Piotr Piotr Indyk Theory of Computation 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 ``works'' if A is a random *dense* matrix, chosen from a proper distribution.In this paper, we investigate this procedure for the case where A is binary and *very sparse*. We show that, both in theory and in practice, sparse matrices are essentially as ``good'' as the dense ones. At the same time, sparse binary matrices provide additional benefits, such as reduced encoding and decoding time. 2008-01-15T14:15:14Z 2008-01-15T14:15:14Z 2008-01-10 MIT-CSAIL-TR-2008-001 http://hdl.handle.net/1721.1/40089 Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 13 p. application/pdf application/postscript |
| spellingShingle | Berinde, Radu Indyk, Piotr Sparse recovery using sparse matrices |
| title | Sparse recovery using sparse matrices |
| title_full | Sparse recovery using sparse matrices |
| title_fullStr | Sparse recovery using sparse matrices |
| title_full_unstemmed | Sparse recovery using sparse matrices |
| title_short | Sparse recovery using sparse matrices |
| title_sort | sparse recovery using sparse matrices |
| url | http://hdl.handle.net/1721.1/40089 |
| work_keys_str_mv | AT berinderadu sparserecoveryusingsparsematrices AT indykpiotr sparserecoveryusingsparsematrices |