Volume 33, Issue 5
The Performance of Orthogonal Multi-Matching Pursuit under the Restricted Isometry Property

Zhiqiang Xu

J. Comp. Math., 33 (2015), pp. 495-516.

Published online: 2015-10

Preview Purchase PDF 4 2631
Export citation
  • Abstract

The orthogonal multi-matching pursuit (OMMP) is a natural extension of the orthogonal matching pursuit (OMP).We denote the OMMP with the parameter $M$ as OMMP($M$) where $M$ ≥ 1 is an integer. The main difference between OMP and OMMP($M$) is that OMMP($M$) selects $M$ atoms per iteration, while OMP only adds one atom to the optimal atom set. In this paper, we study the performance of orthogonal multi-matching pursuit under RIP. In particular, we show that, when the measurement matrix $A$ satisfies (25$s$, 1/10)-RIP, OMMP($M_0$) with $M_0$ = 12 can recover $s$-sparse signals within $s$ iterations. We furthermore prove that OMMP($M$) can recover $s$-sparse signals within $O(s/M)$ iterations for a large class of $M$.

  • Keywords

Sparse signals, Compressed sensing, Greedy algorithms

  • AMS Subject Headings

94A12, 65H99, 65D15.

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

xuzq@lsec.cc.ac.cn (Zhiqiang Xu)

  • BibTex
  • RIS
  • TXT
@Article{JCM-33-495, author = {Xu , Zhiqiang}, title = {The Performance of Orthogonal Multi-Matching Pursuit under the Restricted Isometry Property}, journal = {Journal of Computational Mathematics}, year = {2015}, volume = {33}, number = {5}, pages = {495--516}, abstract = {

The orthogonal multi-matching pursuit (OMMP) is a natural extension of the orthogonal matching pursuit (OMP).We denote the OMMP with the parameter $M$ as OMMP($M$) where $M$ ≥ 1 is an integer. The main difference between OMP and OMMP($M$) is that OMMP($M$) selects $M$ atoms per iteration, while OMP only adds one atom to the optimal atom set. In this paper, we study the performance of orthogonal multi-matching pursuit under RIP. In particular, we show that, when the measurement matrix $A$ satisfies (25$s$, 1/10)-RIP, OMMP($M_0$) with $M_0$ = 12 can recover $s$-sparse signals within $s$ iterations. We furthermore prove that OMMP($M$) can recover $s$-sparse signals within $O(s/M)$ iterations for a large class of $M$.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1505-m4529}, url = {http://global-sci.org/intro/article_detail/jcm/9856.html} }
TY - JOUR T1 - The Performance of Orthogonal Multi-Matching Pursuit under the Restricted Isometry Property AU - Xu , Zhiqiang JO - Journal of Computational Mathematics VL - 5 SP - 495 EP - 516 PY - 2015 DA - 2015/10 SN - 33 DO - http://doi.org/10.4208/jcm.1505-m4529 UR - https://global-sci.org/intro/article_detail/jcm/9856.html KW - Sparse signals, Compressed sensing, Greedy algorithms AB -

The orthogonal multi-matching pursuit (OMMP) is a natural extension of the orthogonal matching pursuit (OMP).We denote the OMMP with the parameter $M$ as OMMP($M$) where $M$ ≥ 1 is an integer. The main difference between OMP and OMMP($M$) is that OMMP($M$) selects $M$ atoms per iteration, while OMP only adds one atom to the optimal atom set. In this paper, we study the performance of orthogonal multi-matching pursuit under RIP. In particular, we show that, when the measurement matrix $A$ satisfies (25$s$, 1/10)-RIP, OMMP($M_0$) with $M_0$ = 12 can recover $s$-sparse signals within $s$ iterations. We furthermore prove that OMMP($M$) can recover $s$-sparse signals within $O(s/M)$ iterations for a large class of $M$.

Zhiqiang Xu. (2020). The Performance of Orthogonal Multi-Matching Pursuit under the Restricted Isometry Property. Journal of Computational Mathematics. 33 (5). 495-516. doi:10.4208/jcm.1505-m4529
Copy to clipboard
The citation has been copied to your clipboard