Backtracking-Based Matching Pursuit Method for Sparse Signal Reconstruction

This letter presents a variant of Orthogonal Matching Pursuit (OMP) method, called Backtracking-based Adaptive OMP (BAOMP), for compressive sensing and sparse signal reconstruction. As an extension of the OMP algorithm, the BAOMP method incorporates a simple backtracking technique to detect the previous chosen atoms' reliability and then deletes the unreliable atoms at each iteration. Through this modification, the BAOMP method achieves superior performance while maintaining the low complexity of OMP-type methods. Also, unlike its several predecessors, the BAOMP method does not require the sparsity level to be known a priori. The experiments demonstrate the proposed method's superior performance to that of several other OMP-type and l(1) optimization methods.