Improved Bounds on RIP for Generalized Orthogonal Matching Pursuit

Generalized Orthogonal Matching Pursuit (gOMP) is a natural extension of OMP algorithm where unlike OMP, it may select $N(\ge 1)$ atoms in each iteration. In this paper, we demonstrate that gOMP can successfully reconstruct a $K$-sparse signal from a compressed measurement $\mathbf{y}=\mathbf{\Phi }\mathbf{x}$ by $K^{th}$ iteration if the sensing matrix $\mathbf{\Phi }$ satisfies restricted isometry property (RIP) of order $NK$ where $\delta_{NK} < \frac {\sqrt{N}}{\sqrt{K}+2\sqrt{N}}$. Our bound offers an improvement over the very recent result shown in \cite{wang_2012b}. Moreover, we present another bound for gOMP of order $NK+1$ with $\delta_{NK+1} < \frac {\sqrt{N}}{\sqrt{K}+\sqrt{N}}$ which exactly relates to the near optimal bound of ${\delta }_{K+1}<\frac{1}{\sqrt{K}+1}$ for OMP (N=1) as shown in \cite{wang_2012a}.