Newton-Step-Based Hard Thresholding Algorithms for Sparse Signal Recovery

Sparse signal recovery or compressed sensing can be formulated as certain sparse optimization problems. The classic optimization theory indicates that the Newton-like method often has a numerical advantage over the classic gradient method for nonlinear optimization problems. In this paper, we propose the so-called Newton-step-based iterative hard thresholding (NSIHT) and the Newton-step-based hard thresholding pursuit (NSHTP) algorithms for sparse signal recovery. Different from the traditional iterative hard thresholding (IHT) and hard thresholding pursuit (HTP), the proposed algorithms adopt the Newton-like search direction instead of the steepest descent direction. A theoretical analysis for the proposed algorithms is carried out, and sufficient conditions for the guaranteed success of sparse signal recovery via these algorithms are established in terms of the restricted isometry property of a sensing matrix which is one of the standard assumptions used in the field of compressed sensing and signal approximation. The empirical results from synthetic signal recovery indicate that the performance of proposed algorithms are comparable to that of several existing algorithms. The numerical behavior of our algorithms with respect to the residual reduction and parameter changes is also investigated through simulations.