Hard thresholding pursuit algorithms: Number of iterations

详细信息    查看全文

• 作者：Jean-Luc Bouchot ; Simon Foucart ; ^{simon.foucart@centraliens.net" class="auth_mail" title="E-mail the corresponding author} ; Pawel Hitczenko
• 关键词：65F10 ; 65J20 ; 15A29 ; 94A12
• 刊名：Applied and Computational Harmonic Analysis
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：41
• 期：2
• 页码：412-435
• 全文大小：1011 K

文摘

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.