Sequential sparse matching pursuit
We propose a new algorithm, called sequential sparse matching pursuit (SSMP), for solving sparse recovery problems. The algorithm provably recovers a k-sparse approximation to an arbitrary n-dimensional signal vector x from only O(k log(n/k)) linear measurements of x. The recovery process takes time...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Online Access: | http://hdl.handle.net/1721.1/58832 https://orcid.org/0000-0002-7983-9524 |
| _version_ | 1826198882767339520 |
|---|---|
| author | Berinde, Radu Indyk, Piotr |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Berinde, Radu Indyk, Piotr |
| author_sort | Berinde, Radu |
| collection | MIT |
| description | We propose a new algorithm, called sequential sparse matching pursuit (SSMP), for solving sparse recovery problems. The algorithm provably recovers a k-sparse approximation to an arbitrary n-dimensional signal vector x from only O(k log(n/k)) linear measurements of x. The recovery process takes time that is only near-linear in n. Preliminary experiments indicate that the algorithm works well on synthetic and image data, with the recovery quality often outperforming that of more complex algorithms, such as à ¿1 minimization. |
| first_indexed | 2024-09-23T11:11:10Z |
| format | Article |
| id | mit-1721.1/58832 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:11:10Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/588322022-10-01T01:54:25Z Sequential sparse matching pursuit Berinde, Radu Indyk, Piotr Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Indyk, Piotr Indyk, Piotr Berinde, Radu We propose a new algorithm, called sequential sparse matching pursuit (SSMP), for solving sparse recovery problems. The algorithm provably recovers a k-sparse approximation to an arbitrary n-dimensional signal vector x from only O(k log(n/k)) linear measurements of x. The recovery process takes time that is only near-linear in n. Preliminary experiments indicate that the algorithm works well on synthetic and image data, with the recovery quality often outperforming that of more complex algorithms, such as à ¿1 minimization. 2010-10-01T18:19:38Z 2010-10-01T18:19:38Z 2009-09 Article http://purl.org/eprint/type/JournalArticle 978-1-4244-5870-7 INSPEC Accession Number: 11135260 http://hdl.handle.net/1721.1/58832 Berinde, R., and P. Indyk. “Sequential Sparse Matching Pursuit.” Communication, Control, and Computing, 2009. Allerton 2009. 47th Annual Allerton Conference on. 2009. 36-43. © 2009, IEEE https://orcid.org/0000-0002-7983-9524 en_US http://dx.doi.org/10.1109/ALLERTON.2009.5394834 Allerton Conference on Communication, Control, and Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Berinde, Radu Indyk, Piotr Sequential sparse matching pursuit |
| title | Sequential sparse matching pursuit |
| title_full | Sequential sparse matching pursuit |
| title_fullStr | Sequential sparse matching pursuit |
| title_full_unstemmed | Sequential sparse matching pursuit |
| title_short | Sequential sparse matching pursuit |
| title_sort | sequential sparse matching pursuit |
| url | http://hdl.handle.net/1721.1/58832 https://orcid.org/0000-0002-7983-9524 |
| work_keys_str_mv | AT berinderadu sequentialsparsematchingpursuit AT indykpiotr sequentialsparsematchingpursuit |