Improved bounds on restricted isometry constant for orthogonal multi matching pursuit

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.