Hard Thresholding Pursuit: An Algorithm for Compressive Sensing

We introduce a new iterative algorithm to find sparse solutions of underdetermined linear systems. The algorithm, a simple combination of the Iterative Hard Thresholding algorithm and the Compressive Sampling Matching Pursuit algorithm, is called Hard Thresholding Pursuit. We study its general convergence and notice in particular that only a finite number of iterations are required. We then show that, under a certain condition on the restricted isometry constant of the matrix of the linear system, the Hard Thresholding Pursuit algorithm indeed finds all s-sparse solutions. This condition, which reads $\delta_{3 s} < 1/\sqrt{3}$, is heuristically better than the sufficient conditions currently available for other compressive sensing algorithms. It applies to fast versions of the algorithm, too, including the Iterative Hard Thresholding algorithm. Stability with respect to sparsity defect and robustness with respect to measurement error are also guaranteed under the condition $\delta_{3 s} < 1/\sqrt{3}$. We conclude with some numerical experiments to demonstrate the good empirical performance and the low complexity of the Hard Thresholding Pursuit algorithm.