The Sufficient Conditions for Orthogonal Matching Pursuit to Exactly Reconstruct Sparse Polynomials

Aitong Huang, Renzhong Feng () and Andong Wang
Additional contact information
Aitong Huang: School of Mathematics Science, Beihang University, Beijing 102200, China
Renzhong Feng: School of Mathematics Science, Beihang University, Beijing 102200, China
Andong Wang: School of Mathematics Science, Beihang University, Beijing 102200, China

Mathematics, 2022, vol. 10, issue 19, 1-23

Abstract: Orthogonal matching pursuit (OMP for short) is a classical method for sparse signal recovery in compressed sensing. In this paper, we consider the application of OMP to reconstruct sparse polynomials generated by uniformly bounded orthonormal systems, which is an extension of the work on OMP to reconstruct sparse trigonometric polynomials. Firstly, in both cases of sampled data with and without noise, sufficient conditions for OMP to recover the coefficient vector of a sparse polynomial are given, which are more loose than the existing results. Then, based on a more accurate estimation of the mutual coherence of a structured random matrix, the recovery guarantees and success probabilities for OMP to reconstruct sparse polynomials are obtained with the help of those sufficient conditions. In addition, the error estimation for the recovered coefficient vector is gained when the sampled data contain noise. Finally, the validity and correctness of the theoretical conclusions are verified by numerical experiments.

Keywords: uniformly bounded orthonormal system; orthogonal matching pursuit method; law of large number; mutual coherence; recovery guarantee (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/19/3703/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/19/3703/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:19:p:3703-:d:937820

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().