On the Recovery Limit of Sparse Signals Using Orthogonal Matching Pursuit

Abstract

Orthogonal matching pursuit (OMP) is a greedy search algorithm popularly being used for the recovery of compressive sensed sparse signals. In this correspondence, we show that if the 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_{K+1}$</tex></formula> of the sensing 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}$</tex></formula> satisfies <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$\delta_{K+1}&lt;{1\over\sqrt{K}+1}$</tex> </formula> then the OMP algorithm can perfectly recover <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 from the compressed 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}$</tex></formula> . Our bound offers a substantial improvement over the recent result of Davenport and Wakin and also closes gap between the recovery bound and fundamental limit over which the perfect recovery of the OMP cannot be guaranteed.