Improved bounds on restricted isometry constant for orthogonal multi matching pursuit

Article type: Research Article

Authors: Wei, Xiujie | Ye, Peixin^*

Affiliations: School of Mathematics and LPMC, Nankai University, Tianjin, China

Correspondence: [*] Corresponding author: Peixin Ye, West zone apartment 8 B-12-204, Nankai University, No. 94 Weijin Road, Tianjin, China. E-mail:yepx@nankai.edu.cn

Abstract: Orthogonal Multi Matching Pursuit (OMMP) is a super greedy-type algorithm for sparse approximation. We analyze the convergence property of OMMP based on Restricted Isometry Property (RIP). Our main conclusion is that if the sampling matrix Φ satisfies the Restricted Isometry Property of order [sK] with isometry constant δ < 1 + 1 / 2\sqrt {K / s} - 1 / 2\sqrt {K / s + 4\sqrt {K / s} } , then OMMP (s) can exactly recover an arbitrary K-sparse signal x from y = Φ x in at most K$ steps.

Keywords: Compressed sensing, K-sparse signal, orthogonal multi matching pursuit, restricted isometry property, restricted isometry constant

DOI: 10.3233/JCM-150576

Journal: Journal of Computational Methods in Sciences and Engineering, vol. 15, no. 4, pp. 737-744, 2015