Logo image
Back
Hard thresholding pursuit algorithms: Number of iterations
Journal article   Open access   Peer reviewed

Hard thresholding pursuit algorithms: Number of iterations

Jean-Luc Bouchot, Simon Foucart and Pawel Hitczenko
Applied and computational harmonic analysis, v 41(2), pp 412-435
Sep 2016
DOI: https://doi.org/10.1016/j.acha.2016.03.002
url
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.705.1885View
SubmittedOpen Access (License Unspecified),  Open
url
https://doi.org/10.1016/j.acha.2016.03.002View
Published, Version of Record (VoR) Open

Abstract

Compressive sensing Hard thresholding Iterative algorithms Nonuniform sparse recovery Random measurements Uniform sparse recovery
The Hard Thresholding Pursuit algorithm for sparse recovery is revisited using a new theoretical analysis. The main result states that all sparse vectors can be exactly recovered from compressive linear measurements in a number of iterations at most proportional to the sparsity level as soon as the measurement matrix obeys a certain restricted isometry condition. The recovery is also robust to measurement error. The same conclusions are derived for a variation of Hard Thresholding Pursuit, called Graded Hard Thresholding Pursuit, which is a natural companion to Orthogonal Matching Pursuit and runs without a prior estimation of the sparsity level. In addition, for two extreme cases of the vector shape, it is shown that, with high probability on the draw of random measurements, a fixed sparse vector is robustly recovered in a number of iterations precisely equal to the sparsity level. These theoretical findings are experimentally validated, too.

Metrics

12 Record Views
56 citations in Web of Science
54 citations in Scopus

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Web of Science research areas
Mathematics, Applied
Logo image