Improved RIP-Based Bounds for Guaranteed Performance of Two Compressed Sensing Algorithms

Iterative hard thresholding (IHT) and compressive sampling matching pursuit (CoSaMP) are two mainstream compressed sensing algorithms using the hard thresholding operator. The guaranteed performance of the two algorithms for signal recovery was mainly analyzed in terms of the restricted isometry property (RIP) of sensing matrices. At present, the best known bound using RIP of order $3k$ for guaranteed performance of IHT (with unit stepsize) is $\delta_{3k}< 1/\sqrt{3}\approx 0.5774,$ and the bound for CoSaMP using RIP of order $4k$ is $\delta_{4k} < 0.4782. $ A fundamental question in this area is whether such theoretical results can be further improved. The purpose of this paper is to affirmatively answer this question and to rigorously show that the above-mentioned RIP bound for guaranteed performance of IHT can be significantly improved to $ \delta_{3k} < (\sqrt{5}-1)/2 \approx 0.618, $ and the bound for CoSaMP can be improved to $ \delta_{4k}< 0.5102. $

Article

Download

View PDF