Sequential Compressed Sensing
Compressed sensing allows perfect recovery of sparse signals (or signals sparse in some basis) using only a small number of random measurements. Existing results in compressed sensing literature have focused on characterizing the achievable performance by bounding the number of samples required for...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers ; IEEE Signal Processing Society
2011
|
| Online Access: | http://hdl.handle.net/1721.1/61416 https://orcid.org/0000-0003-0149-5888 |
| _version_ | 1826211626168090624 |
|---|---|
| author | Malioutov, Dmitry M. Sanghavi, Sujay R. Willsky, Alan S. |
| 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 Malioutov, Dmitry M. Sanghavi, Sujay R. Willsky, Alan S. |
| author_sort | Malioutov, Dmitry M. |
| collection | MIT |
| description | Compressed sensing allows perfect recovery of sparse signals (or signals sparse in some basis) using only a small number of random measurements. Existing results in compressed sensing literature have focused on characterizing the achievable performance by bounding the number of samples required for a given level of signal sparsity. However, using these bounds to minimize the number of samples requires a priori knowledge of the sparsity of the unknown signal, or the decay structure for near-sparse signals. Furthermore, there are some popular recovery methods for which no such bounds are known. In this paper, we investigate an alternative scenario where observations are available in sequence. For any recovery method, this means that there is now a sequence of candidate reconstructions. We propose a method to estimate the reconstruction error directly from the samples themselves, for every candidate in this sequence. This estimate is universal in the sense that it is based only on the measurement ensemble, and not on the recovery method or any assumed level of sparsity of the unknown signal. With these estimates, one can now stop observations as soon as there is reasonable certainty of either exact or sufficiently accurate reconstruction. They also provide a way to obtain ??run-time?? guarantees for recovery methods that otherwise lack a priori performance bounds. We investigate both continuous (e.g., Gaussian) and discrete (e.g., Bernoulli) random measurement ensembles, both for exactly sparse and general near-sparse signals, and with both noisy and noiseless measurements. |
| first_indexed | 2024-09-23T15:08:57Z |
| format | Article |
| id | mit-1721.1/61416 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:08:57Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers ; IEEE Signal Processing Society |
| record_format | dspace |
| spelling | mit-1721.1/614162022-09-29T13:01:18Z Sequential Compressed Sensing Malioutov, Dmitry M. Sanghavi, Sujay R. Willsky, Alan S. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Willsky, Alan S. Malioutov, Dmitry M. Willsky, Alan S. Compressed sensing allows perfect recovery of sparse signals (or signals sparse in some basis) using only a small number of random measurements. Existing results in compressed sensing literature have focused on characterizing the achievable performance by bounding the number of samples required for a given level of signal sparsity. However, using these bounds to minimize the number of samples requires a priori knowledge of the sparsity of the unknown signal, or the decay structure for near-sparse signals. Furthermore, there are some popular recovery methods for which no such bounds are known. In this paper, we investigate an alternative scenario where observations are available in sequence. For any recovery method, this means that there is now a sequence of candidate reconstructions. We propose a method to estimate the reconstruction error directly from the samples themselves, for every candidate in this sequence. This estimate is universal in the sense that it is based only on the measurement ensemble, and not on the recovery method or any assumed level of sparsity of the unknown signal. With these estimates, one can now stop observations as soon as there is reasonable certainty of either exact or sufficiently accurate reconstruction. They also provide a way to obtain ??run-time?? guarantees for recovery methods that otherwise lack a priori performance bounds. We investigate both continuous (e.g., Gaussian) and discrete (e.g., Bernoulli) random measurement ensembles, both for exactly sparse and general near-sparse signals, and with both noisy and noiseless measurements. United States. Army Research Office (Grant W911NF-05-1-0207) United States. Air Force Office of Scientific Research (Grant FA9550-04-1-0351) 2011-03-04T19:17:26Z 2011-03-04T19:17:26Z 2010-04 2009-10 Article http://purl.org/eprint/type/JournalArticle 1932-4553 INSPEC Accession Number: 11172106 http://hdl.handle.net/1721.1/61416 Malioutov, D.M., S.R. Sanghavi, and A.S. Willsky. “Sequential Compressed Sensing.” Selected Topics in Signal Processing, IEEE Journal of 4.2 (2010): 435-444. © 2010, IEEE https://orcid.org/0000-0003-0149-5888 en_US http://dx.doi.org/10.1109/jstsp.2009.2038211 IEEE journal of selected topics in signal processing 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 Signal Processing Society IEEE |
| spellingShingle | Malioutov, Dmitry M. Sanghavi, Sujay R. Willsky, Alan S. Sequential Compressed Sensing |
| title | Sequential Compressed Sensing |
| title_full | Sequential Compressed Sensing |
| title_fullStr | Sequential Compressed Sensing |
| title_full_unstemmed | Sequential Compressed Sensing |
| title_short | Sequential Compressed Sensing |
| title_sort | sequential compressed sensing |
| url | http://hdl.handle.net/1721.1/61416 https://orcid.org/0000-0003-0149-5888 |
| work_keys_str_mv | AT malioutovdmitrym sequentialcompressedsensing AT sanghavisujayr sequentialcompressedsensing AT willskyalans sequentialcompressedsensing |