Volume 34, Issue 1
The Exact Recovery of Sparse Signals Via Orthogonal Matching Pursuit

Anping Liao, Jiaxin Xie, Xiaobo Yang & Peng Wang

J. Comp. Math., 34 (2016), pp. 70-86.

Published online: 2016-02

Preview Full PDF 544 2526
Export citation
  • Abstract

This paper aims to investigate sufficient conditions for the recovery of sparse signals via the orthogonal matching pursuit (OMP) algorithm. In the noiseless case, we present a novel sufficient condition for the exact recovery of all k-sparse signals by the OMP algorithm, and demonstrate that this condition is sharp. In the noisy case, a sufficient condition for recovering the support of k-sparse signal is also presented. Generally, the computation for the restricted isometry constant (RIC) in these sufficient conditions is typically difficult, therefore we provide a new condition which is not only computable but also sufficient for the exact recovery of all k-sparse signals.

  • Keywords

Compressed sensing Sparse signal recovery Restricted orthogonality constant (ROC) Restricted isometry constant (RIC) Orthogonal matching pursuit (OMP)

  • AMS Subject Headings

90C90 94A12 65J22 15A29.

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

xiaoboyang@hnu.edu.cn (Anping Liao)

xiejiaxin@hnu.edu.cn (Jiaxin Xie)

liaoap@hnu.edu.cn (Xiaobo Yang)

p_wong@126.com (Peng Wang)

  • BibTex
  • RIS
  • TXT
@Article{JCM-34-70, author = {Liao , Anping and Xie , Jiaxin and Yang , Xiaobo and Wang , Peng }, title = {The Exact Recovery of Sparse Signals Via Orthogonal Matching Pursuit}, journal = {Journal of Computational Mathematics}, year = {2016}, volume = {34}, number = {1}, pages = {70--86}, abstract = { This paper aims to investigate sufficient conditions for the recovery of sparse signals via the orthogonal matching pursuit (OMP) algorithm. In the noiseless case, we present a novel sufficient condition for the exact recovery of all k-sparse signals by the OMP algorithm, and demonstrate that this condition is sharp. In the noisy case, a sufficient condition for recovering the support of k-sparse signal is also presented. Generally, the computation for the restricted isometry constant (RIC) in these sufficient conditions is typically difficult, therefore we provide a new condition which is not only computable but also sufficient for the exact recovery of all k-sparse signals.}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1510-m2015-0284}, url = {http://global-sci.org/intro/article_detail/jcm/9783.html} }
TY - JOUR T1 - The Exact Recovery of Sparse Signals Via Orthogonal Matching Pursuit AU - Liao , Anping AU - Xie , Jiaxin AU - Yang , Xiaobo AU - Wang , Peng JO - Journal of Computational Mathematics VL - 1 SP - 70 EP - 86 PY - 2016 DA - 2016/02 SN - 34 DO - http://doi.org/10.4208/jcm.1510-m2015-0284 UR - https://global-sci.org/intro/article_detail/jcm/9783.html KW - Compressed sensing KW - Sparse signal recovery KW - Restricted orthogonality constant (ROC) KW - Restricted isometry constant (RIC) KW - Orthogonal matching pursuit (OMP) AB - This paper aims to investigate sufficient conditions for the recovery of sparse signals via the orthogonal matching pursuit (OMP) algorithm. In the noiseless case, we present a novel sufficient condition for the exact recovery of all k-sparse signals by the OMP algorithm, and demonstrate that this condition is sharp. In the noisy case, a sufficient condition for recovering the support of k-sparse signal is also presented. Generally, the computation for the restricted isometry constant (RIC) in these sufficient conditions is typically difficult, therefore we provide a new condition which is not only computable but also sufficient for the exact recovery of all k-sparse signals.
Anping Liao , Jiaxin Xie , Xiaobo Yang & Peng Wang . (2019). The Exact Recovery of Sparse Signals Via Orthogonal Matching Pursuit. Journal of Computational Mathematics. 34 (1). 70-86. doi:10.4208/jcm.1510-m2015-0284
Copy to clipboard
The citation has been copied to your clipboard