Coherence-based performance analysis of the generalized orthogonal matching pursuit algorithm

The performance guarantees of generalized orthogonal matching pursuit (gOMP) are considered in the framework of mutual coherence. The gOMP algorithm is an extension of the well-known OMP greed algorithm for compressed sensing. It identifies multiple N indices per iteration to reconstruct sparse signals. The gOMP with N≥2 can perfectly reconstruct any K-sparse signals from measurement y=Φx if K<1/N(1/μ-1)+1, where μ is coherence parameter of measurement matrix Φ. Furthermore, the performance of the gOMP in the case of y=Φx+e with bounded noise ‖e‖₂≤ε is analyzed and the sufficient condition ensuring identification of correct indices of sparse signals via the gOMP is derived, i.e., K<1/N(1/μ-1)+1-(2ε)/(Nμx_min), where x_min denotes the minimum magnitude of the nonzero elements of x. Similarly, the sufficient condition in the case of Gaussian noise is also given.