A Novel Sufficient Condition for Generalized Orthogonal Matching Pursuit

Abstract

Generalized orthogonal matching pursuit (gOMP), also called orthogonal multi-matching pursuit, is an extension of OMP in the sense that N ≥ 1 indices are identified per iteration. In this letter, we show that if the restricted isometry constant σ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">NK+1</sub> of a sensing matrix A satisfies σ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">NK+1</sub> <; 1/(K/N + 1) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/2</sup> , then under a condition on the signal-to-noise ratio, gOMP identifies at least one index in the support of any K-sparse signal x from y = Ax + v at each iteration, where v is a noise vector. Surprisingly, this condition does not require N ≤ K which is needed in Wang et al. and Liu et al. Thus, N can have more choices. When N = 1, it reduces to be a sufficient condition for OMP, which is less restrictive than that proposed in Wang et al. Moreover, in the noise-free case, it is a sufficient condition for accurately recovering x in K iterations, which is less restrictive than the best known one. In particular, it reduces to the sharp condition proposed in Mo 2015 when N = 1.