Signal Recovery from Random Measurements via Extended Orthogonal Matching Pursuit

Orthogonal Matching Pursuit (OMP) and Basis Pursuit (BP) are two well-known recovery algorithms in compressed sensing. To recover ad-dimensionalm-sparse signal with high probability, OMP needsO(mlnd)number of measurements, whereas BP needs onlyO(mlnd m)number of measurements. In contrary, OMP is a practically more appealing algorithm due to its superior execution speed. In this piece of work, we have proposed a scheme that brings the required number of measurements for OMP closer to BP. We have termed this scheme asOMPα, which runs OMP for(m+αm)-iterations instead ofm-iterations, by choosing a value ofα∈[0,1]. It is shown thatOMPαguarantees a high probability signal recovery withO(mlndαm+1)number of measurements. Another limitation of OMP unlike BP is that it requires the knowledge ofm. In order to overcome this limitation, we have extended the idea ofOMPαto illustrate another recovery scheme calledOMP∞, which runs OMP until the signal residue vanishes. It is shown thatOMP∞can achieve a close to₀-norm recovery without any knowledge ofmlike BP.