Accelerated over-relaxation heavy-ball hard thresholding pursuit for compressive sensing

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.