From theoretical guarantee to practical performance: selectable and optimal step-lengths for IHT and HTP algorithms in compressed sensing

In this study, we present some new findings regarding the selection of step-lengths for two hard thresholding-based algorithms in compressed sensing, namely, iterative hard thresholding (IHT) and hard thresholding pursuit (HTP). Firstly, we establish bounds for the restricted isometry constant (RIC) as functions incorporating a variable step-length instead of a fixed value. Based on these derived bounds, we deduce theoretical selectable step-lengths that ensure the convergence of both algorithms under the sufficient conditions based on RIC of order 3s. Secondly, extensive numerical experiments show that the empirically optimal step-length is usually not identical to the theoretically optimal one, which is typically a unit step-length frequently used in previous literature. We provide empirically optimal step-lengths for three different shapes of sparse signals under Gaussian measurements for practical applications.