Support Recovery from Noisy Measurement via Orthogonal Multi-Matching Pursuit

Abstract

In this paper, a new stopping rule is proposed for orthogonal multi-matching pursuit (OMMP). We show that, for $ℓ_2$ bounded noise case, OMMP with the new stopping rule can recover the true support of any $K$-sparse signal $x$ from noisy measurements $y = Φx + e$ in at most $K$ iterations, provided that all the nonzero components of $x$ and the elements of the matrix $Φ$ satisfy certain requirements. The proposed method can improve the existing result. In particular, for the noiseless case, OMMP can exactly recover any $K$-sparse signal under the same RIP condition.