arrow
Volume 15, Issue 3
The Recovery Guarantee for Orthogonal Matching Pursuit Method to Reconstruct Sparse Polynomials

Aitong Huang, Renzhong Feng & Sanpeng Zheng

Numer. Math. Theor. Meth. Appl., 15 (2022), pp. 793-818.

Published online: 2022-07

Export citation
  • Abstract

Orthogonal matching pursuit (OMP for short) algorithm is a popular method of sparse signal recovery in compressed sensing. This paper applies OMP to the sparse polynomial reconstruction problem. Distinguishing from classical research methods using mutual coherence or restricted isometry property of the measurement matrix, the recovery guarantee and the success probability of OMP are obtained directly by the greedy selection ratio and the probability theory. The results show that the failure probability of OMP given in this paper is exponential small with respect to the number of sampling points. In addition, the recovery guarantee of OMP obtained through classical methods is lager than that of $ℓ_1$-minimization whatever the sparsity of sparse polynomials is, while the recovery guarantee given in this paper is roughly the same as that of $ℓ_1$-minimization when the sparsity is less than 93. Finally, the numerical experiments verify the availability of the theoretical results.

  • AMS Subject Headings

41A10, 41A05, 65D15

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{NMTMA-15-793, author = {Huang , AitongFeng , Renzhong and Zheng , Sanpeng}, title = {The Recovery Guarantee for Orthogonal Matching Pursuit Method to Reconstruct Sparse Polynomials}, journal = {Numerical Mathematics: Theory, Methods and Applications}, year = {2022}, volume = {15}, number = {3}, pages = {793--818}, abstract = {

Orthogonal matching pursuit (OMP for short) algorithm is a popular method of sparse signal recovery in compressed sensing. This paper applies OMP to the sparse polynomial reconstruction problem. Distinguishing from classical research methods using mutual coherence or restricted isometry property of the measurement matrix, the recovery guarantee and the success probability of OMP are obtained directly by the greedy selection ratio and the probability theory. The results show that the failure probability of OMP given in this paper is exponential small with respect to the number of sampling points. In addition, the recovery guarantee of OMP obtained through classical methods is lager than that of $ℓ_1$-minimization whatever the sparsity of sparse polynomials is, while the recovery guarantee given in this paper is roughly the same as that of $ℓ_1$-minimization when the sparsity is less than 93. Finally, the numerical experiments verify the availability of the theoretical results.

}, issn = {2079-7338}, doi = {https://doi.org/10.4208/nmtma.OA-2022-0015}, url = {http://global-sci.org/intro/article_detail/nmtma/20816.html} }
TY - JOUR T1 - The Recovery Guarantee for Orthogonal Matching Pursuit Method to Reconstruct Sparse Polynomials AU - Huang , Aitong AU - Feng , Renzhong AU - Zheng , Sanpeng JO - Numerical Mathematics: Theory, Methods and Applications VL - 3 SP - 793 EP - 818 PY - 2022 DA - 2022/07 SN - 15 DO - http://doi.org/10.4208/nmtma.OA-2022-0015 UR - https://global-sci.org/intro/article_detail/nmtma/20816.html KW - Reconstruction of sparse polynomial, uniformly bounded orthogonal system, orthogonal matching pursuit method, probability of successful reconstruction, sub-Gaussian random variable. AB -

Orthogonal matching pursuit (OMP for short) algorithm is a popular method of sparse signal recovery in compressed sensing. This paper applies OMP to the sparse polynomial reconstruction problem. Distinguishing from classical research methods using mutual coherence or restricted isometry property of the measurement matrix, the recovery guarantee and the success probability of OMP are obtained directly by the greedy selection ratio and the probability theory. The results show that the failure probability of OMP given in this paper is exponential small with respect to the number of sampling points. In addition, the recovery guarantee of OMP obtained through classical methods is lager than that of $ℓ_1$-minimization whatever the sparsity of sparse polynomials is, while the recovery guarantee given in this paper is roughly the same as that of $ℓ_1$-minimization when the sparsity is less than 93. Finally, the numerical experiments verify the availability of the theoretical results.

Aitong Huang, Renzhong Feng & Sanpeng Zheng. (2022). The Recovery Guarantee for Orthogonal Matching Pursuit Method to Reconstruct Sparse Polynomials. Numerical Mathematics: Theory, Methods and Applications. 15 (3). 793-818. doi:10.4208/nmtma.OA-2022-0015
Copy to clipboard
The citation has been copied to your clipboard