Signal recovery from random measurements via extended orthogonal matching pursuit
Orthogonal Matching Pursuit (OMP) and Basis Pursuit (BP) are two well-known recovery algorithms in compressed sensing. To recover a d-dimensional m-sparse signal with high probability, OMP needs O (mln d) number of measurements, whereas BP needs only O mln d m number of measurements. In contrary, OM...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2015
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/107083 http://hdl.handle.net/10220/25302 http://dx.doi.org/10.1109/TSP.2015.2413384 |
| _version_ | 1826122997273985024 |
|---|---|
| author | Sahoo, Sujit Kumar Makur, Anamitra |
| author2 | School of Electrical and Electronic Engineering |
| author_facet | School of Electrical and Electronic Engineering Sahoo, Sujit Kumar Makur, Anamitra |
| author_sort | Sahoo, Sujit Kumar |
| collection | NTU |
| description | Orthogonal Matching Pursuit (OMP) and Basis Pursuit (BP) are two well-known recovery algorithms in compressed sensing. To recover a d-dimensional m-sparse signal with high probability, OMP needs O (mln d) number of measurements, whereas BP needs only O mln d m number of measurements. In contrary, OMP is a practically more appealing algorithm due to its superior execution speed. In this piece of work, we have proposed a scheme that brings the required number of measurements for OMP closer to BP. We have termed this scheme as OMPα, which runs OMP for (m + αm)-iterations instead of m-iterations, by choosing a value of α ??? [0, 1]. It is shown that OMPα guarantees a high probability signal recovery with O mln d αm+1 number of measurements. Another limitation of OMP unlike BP is that it requires the knowledge of m. In order to overcome this limitation, we have extended the idea of OMPα to illustrate another recovery scheme called OMP∞, which runs OMP until the signal residue vanishes. It is shown that OMP∞ can achieve a close to 0-norm recovery without any knowledge of m like BP. |
| first_indexed | 2024-10-01T05:57:25Z |
| format | Journal Article |
| id | ntu-10356/107083 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:57:25Z |
| publishDate | 2015 |
| record_format | dspace |
| spelling | ntu-10356/1070832019-12-06T22:24:20Z Signal recovery from random measurements via extended orthogonal matching pursuit Sahoo, Sujit Kumar Makur, Anamitra School of Electrical and Electronic Engineering DRNTU::Engineering::Electrical and electronic engineering::Electronic systems::Signal processing Orthogonal Matching Pursuit (OMP) and Basis Pursuit (BP) are two well-known recovery algorithms in compressed sensing. To recover a d-dimensional m-sparse signal with high probability, OMP needs O (mln d) number of measurements, whereas BP needs only O mln d m number of measurements. In contrary, OMP is a practically more appealing algorithm due to its superior execution speed. In this piece of work, we have proposed a scheme that brings the required number of measurements for OMP closer to BP. We have termed this scheme as OMPα, which runs OMP for (m + αm)-iterations instead of m-iterations, by choosing a value of α ??? [0, 1]. It is shown that OMPα guarantees a high probability signal recovery with O mln d αm+1 number of measurements. Another limitation of OMP unlike BP is that it requires the knowledge of m. In order to overcome this limitation, we have extended the idea of OMPα to illustrate another recovery scheme called OMP∞, which runs OMP until the signal residue vanishes. It is shown that OMP∞ can achieve a close to 0-norm recovery without any knowledge of m like BP. Accepted version 2015-03-30T08:41:49Z 2019-12-06T22:24:20Z 2015-03-30T08:41:49Z 2019-12-06T22:24:20Z 2015 2015 Journal Article Sahoo, S. K., & Makur, A. (2015). Signal recovery from random measurements via extended orthogonal matching pursuit. IEEE transactions on signal processing, 63(10), 2572-2581. https://hdl.handle.net/10356/107083 http://hdl.handle.net/10220/25302 http://dx.doi.org/10.1109/TSP.2015.2413384 183898 en IEEE transactions on signal processing © 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: [http://dx.doi.org/10.1109/TSP.2015.2413384]. 10 p. application/pdf |
| spellingShingle | DRNTU::Engineering::Electrical and electronic engineering::Electronic systems::Signal processing Sahoo, Sujit Kumar Makur, Anamitra Signal recovery from random measurements via extended orthogonal matching pursuit |
| title | Signal recovery from random measurements via extended orthogonal matching pursuit |
| title_full | Signal recovery from random measurements via extended orthogonal matching pursuit |
| title_fullStr | Signal recovery from random measurements via extended orthogonal matching pursuit |
| title_full_unstemmed | Signal recovery from random measurements via extended orthogonal matching pursuit |
| title_short | Signal recovery from random measurements via extended orthogonal matching pursuit |
| title_sort | signal recovery from random measurements via extended orthogonal matching pursuit |
| topic | DRNTU::Engineering::Electrical and electronic engineering::Electronic systems::Signal processing |
| url | https://hdl.handle.net/10356/107083 http://hdl.handle.net/10220/25302 http://dx.doi.org/10.1109/TSP.2015.2413384 |
| work_keys_str_mv | AT sahoosujitkumar signalrecoveryfromrandommeasurementsviaextendedorthogonalmatchingpursuit AT makuranamitra signalrecoveryfromrandommeasurementsviaextendedorthogonalmatchingpursuit |