Improved Bounds on RIP for Generalized Orthogonal Matching Pursuit

Abstract

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 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}.

8 pages, 1 figure

References in corpus (1)

• Generalized Orthogonal Matching Pursuit