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 Nindices per iteration to reconstruct sparse signals. The gOMP with N≥2 can perfectly reconstruct any K-sparse signals from measurement y= Φxif 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+ ewith 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 _mindenotes the minimum magnitude of the nonzero elements of x. Similarly, the sufficient condition in the case of Gaussian noise is also given.