In this paper, we propose a novel algorithm, called Accelerated Over-Relaxation Heavy-Ball Hard Threshold Pursuit (AOR-HBHTP), for solving compressive sensing problems. The algorithm incorporates the Accelerated Over-Relaxation technique and Heavy-Ball momentum into the Hard Threshold Pursuit framework. Theoretical results include establishing convergence analysis and providing an estimation of the number of iteration steps. We show that, as long as the measurement matrix satisfies the restricted isometry property, AOR-HBHTP can successfully recover unknown signals within a number of iterations proportional to the sparsity level. The upper bound on the number of iterations is uniform in the sense that it does not depend on any unknown special-signal information. In numerical experiments, we evaluate recovery capability, success rate, and runtime of AOR-HBHTP by using Phase Transition Curve, Algorithm Selection Map, and Signal-to-Noise Ratio. The promising numerical results demonstrate the effectiveness of AOR-HBHTP in recovering sparse signals.

Hard Thresholding Pursuit (HTP) is one of the important and efficient algorithms for reconstructing sparse signals. Unfortunately, the hard thresholding operator is independent of the objective function and hence leads to numerical oscillation in the course of iterations. To alleviate this drawback, the hard thresholding operator should be applied to a compressible vector. Motivated by this idea, we propose a new algorithm called Compressive Hard Thresholding Pursuit (CHTP) by introducing a compressive step first to the standard HTP. Convergence analysis and stability of CHTP are established in terms of the restricted isometry property of a sensing matrix. Numerical experiments show that CHTP is competitive with other mainstream algorithms such as the HTP, Orthogonal Matching Pursuit (OMP) and Subspace Pursuit (SP) algorithms both in the sparse signal reconstruction ability and average recovery runtime.