HARD THRESHOLDING PURSUIT: AN ALGORITHM FOR COMPRESSIVE SENSING Academic Article uri icon

abstract

  • 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 ssparse solutions. This condition, which reads 3s > 1/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 3s > 1/3. We conclude with some numerical experiments to demonstrate the good empirical performance and the low complexity of the Hard Thresholding Pursuit algorithm. 2011 Society for Industrial and Applied Mathematics.

published proceedings

  • SIAM JOURNAL ON NUMERICAL ANALYSIS

author list (cited authors)

  • Foucart, S.

citation count

  • 263

complete list of authors

  • Foucart, Simon

publication date

  • January 2011