Improving the Bound on the RIP Constant in Generalized Orthogonal Matching Pursuit

The generalized Orthogonal Matching Pursuit (gOMP) is a recently proposed compressive sensing greedy recovery algorithm which generalizes the OMP algorithm by selecting N( ≥ 1) atoms in each iteration. In this letter, we demonstrate that the gOMP can successfully reconstruct a K-sparse signal from a compressed measurement y=Φx by a maximum of K iterations if the sensing matrix Φ satisfies the Restricted Isometry Property (RIP) of order NK, with the RIP constant δ_NK satisfying δ_NK <; √N/√K+2√N. The proposed bound is an improvement over the existing bound on δ_NK. We also show that by increasing the RIP order just by one (i.e., NK+1 from NK), it is possible to refine the bound further to δ_NK+1 <; √N/√K+√N, which is consistent (for N=1) with the near optimal bound on δ_K+1 in OMP.