The Recovery Guarantee for Orthogonal Matching Pursuit Method to Reconstruct Sparse Polynomials

作     者：Aitong Huang Renzhong Feng Sanpeng Zheng 

作者机构：School of Mathematics Science&Key Laboratory of MathematicsInformatics and Behavioral SemanticsMinistry of EducationBeihang UniversityBeijingChina 

出 版 物：《Numerical Mathematics(Theory,Methods and Applications)》 (高等学校计算数学学报（英文版）)

年 卷 期：2022年第15卷第3期

页      面：793-818页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：supported by the National Natural Science Foundation of China(Grant No.12071019) 

主　　题：Reconstruction of sparse polynomial uniformly bounded orthogonal system orthogonal matching pursuit method probability of successful reconstruction sub-Gaussian random variable 

摘      要：Orthogonal matching pursuit(OMP for short)algorithm is a popular method of sparse signal recovery in compressed *** paper applies OMP to the sparse polynomial reconstruction *** 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 *** results show that the failure probability of OMP given in this paper is exponential small with respect to the number of sampling *** 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 ***,the numerical experiments verify the availability of the theoretical results.