Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit

Abstract

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> This paper demonstrates theoretically and empirically that a greedy algorithm called Orthogonal Matching Pursuit (OMP) can reliably recover a signal with <emphasis><formula formulatype="inline"><tex>$m$</tex></formula></emphasis> nonzero entries in dimension <emphasis><formula formulatype="inline"><tex>$d$</tex> </formula></emphasis> given <emphasis><formula formulatype="inline"><tex>$ {\rm O}(m \ln d)$</tex></formula></emphasis> random linear measurements of that signal. This is a massive improvement over previous results, which require <emphasis><formula formulatype="inline"><tex>${\rm O}(m^{2})$</tex></formula></emphasis> measurements. The new results for OMP are comparable with recent results for another approach called Basis Pursuit (BP). In some settings, the OMP algorithm is faster and easier to implement, so it is an attractive alternative to BP for signal recovery problems. </para>