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

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.