Abstract view
A sharp bound on RIC in generalized orthogonal matching pursuit


Wengu Chen,
Institute of Applied Physics and Computational Mathematics, Beijing, 100088, China
Huanmin Ge,
Graduate School, China Academy of Engineering Physics, Beijing, 100088, China
Abstract
Generalized orthogonal matching pursuit (gOMP) algorithm has
received much attention in recent years as a natural extension
of
orthogonal matching pursuit (OMP). It is used to recover sparse
signals in compressive sensing. In this paper, a new bound is
obtained for the exact reconstruction of every $K$sparse signal
via
the gOMP algorithm in the noiseless case. That is, if the restricted
isometry constant (RIC) $\delta_{NK+1}$ of the sensing matrix
$A$
satisfies $ \delta_{NK+1}\lt \frac{1}{\sqrt{\frac{K}{N}+1}}$, then
the
gOMP can perfectly recover every $K$sparse signal $x$ from $y=Ax$.
Furthermore, the bound is proved to be sharp.
In the noisy case, the above bound on RIC combining with an
extra condition on the minimum
magnitude of the nonzero components of $K$sparse signals can
guarantee
that the gOMP selects all of support indices of the $K$sparse
signals.