Theoretical results for sparse signal recovery with noises using generalized OMP algorithm

• Sufficient conditions along with stopping rules for the gOMP algorithm are given in noisy compressive sensing.
• The noises are two norm bounded, correlation bounded and Gaussian noises.
• Whole or parts of the support can be recovered with the given conditions.
• Effectiveness of each iteration of the gOMP algorithm is also considered.

The generalized Orthogonal Matching Pursuit (gOMP) algorithm generalizes the OMP algorithm by selecting more than one atom in each iteration. Under conventional settings, the gOMP algorithm iterates K loops where K is the sparsity of the sparse signal that is to be recovered. Thus, K is usually unknown beforehand. We propose stopping rules along with sufficient conditions for the gOMP algorithm to recover the whole or a part of the sparse signal support from noisy observations. It is proved that under conditions on restricted isometry constant (RIC) and magnitude of nonzero elements of the sparse signal, the gOMP algorithm will recover the support with given stopping rules under various noisy settings. We also give conditions under which partial support corresponding to components with significant magnitude of the sparse signal can be recovered.