Recovery of Sparse Signals via Generalized Orthogonal Matching Pursuit: A New Analysis

Abstract

As an extension of orthogonal matching pursuit (OMP) for improving the recovery performance of sparse signals, generalized OMP (gOMP) has recently been studied in the literature. In this paper, we present a new analysis of the gOMP algorithm using the restricted isometry property (RIP). We show that if a measurement matrix <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\mmb\Phi}\in{\cal R}^{m\times n}$</tex></formula> satisfies the RIP with isometry constant <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$\delta_{\max\{9,S+1\}K}\leq{1\over 8}$</tex></formula> , then gOMP performs stable reconstruction of all <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$K$</tex></formula> -sparse signals <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\bf x}\in{\cal R}^{n}$</tex></formula> from the noisy measurements <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\bf y}={\mmb\Phi}{\bf x}+{\bf v}$</tex></formula> , within <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$\max\left\{K,\left\lfloor{8K\over S}\right\rfloor\right\}$</tex> </formula> iterations, where <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\bf v}$</tex></formula> is the noise vector and <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$S$</tex></formula> is the number of indices chosen in each iteration of the gOMP algorithm. For Gaussian random measurements, our result indicates that the number of required measurements is essentially <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$m={\cal O}\left(K\log{n\over K}\right)$</tex> </formula> , which is a significant improvement over the existing result <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$m={\cal O}\left(K^{2}\log{n\over K}\right)$</tex></formula> , especially for large <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$K$</tex></formula> .