Improved RIC Bounds in Terms of δ2s for Hard Thresholding-Based Algorithms

Iterative hard thresholding (IHT) and hard thresholding pursuit (HTP) are two kinds of classical hard thresholding-based algorithms widely used in compressed sensing. Restricted isometry constant (RIC) of sensing matrix which ensures the convergence of iterative algorithms plays a key role in guaranteeing successful recovery. In the analysis of sufficient condition to ensure recovery performance, the RIC δ3s is generally used in previous literature, while δ2s is rarely addressed. In this letter, we first show that the theoretical optimal step-length is 1 while using sufficient condition in terms of δ2s . Furthermore, based on this optimal step-length, the RIC bound is greatly improved to δ2s <(5–√−1)/(23–√)≈0.3568  compared to the existing one δ2s <0.25  for IHT algorithm. Meanwhile, the RIC condition δ2s <7–√/7≈0.3780  is developed for successful recovery via HTP algorithm. As far as we know, this is the first sufficient condition in terms of δ2s for HTP algorithm.