Volume 33, Issue 5
The Performance of Orthogonal Multi-Matching Pursuit under the Restricted Isometry Property

Zhiqiang Xu


J. Comp. Math., 33 (2015), pp. 495-516.

Preview Full PDF BiBTex 1 318
  • Abstract

The orthogonal multi-matching pursuit (OMMP) is a natural extension of the orthogonal matching pursuit (OMP).We denote the OMMP with the parameter M as OMMP(M) where M ≥ 1 is an integer. The main difference between OMP and OMMP(M) is that OMMP(M) selects M atoms per iteration, while OMP only adds one atom to the optimal atom set. In this paper, we study the performance of orthogonal multi-matching pursuit under RIP. In particular, we show that, when the measurement matrix A satisfies (25s, 1/10)-RIP, OMMP(M_0) with M_0 = 12 can recover s-sparse signals within s iterations. We furthermore prove that OMMP(M) can recover s-sparse signals within O(s/M) iterations for a large class of M.

  • History

Published online: 2015-10

  • AMS Subject Headings

94A12, 65H99, 65D15.

  • Cited by