Optimal k-thresholding algorithms for sparse optimization problems

The simulations indicate that the existing hard thresholding technique independent of any residual function may cause a dramatic increase and numerical oscillation of the residual. This inherit drawback of traditional hard thresholdings renders the corresponding algorithms unstable and thus generally inefficient for solving practical sparse optimization problems. How to overcome this weakness and develop a truly efficient thresholding method becomes a fundamental question in this field. The aim of this paper is to affirmatively address this question by proposing a new thresholding technique based on the notion of optimal $k$-thresholding. The central idea for this new development is to enable $k$-thresholding to be connected directly to the residual reduction during the course of algorithms.
This leads to a natural design principle for efficient thresholding algorithms. Under the restricted isometric property (RIP), we prove that the proposed (optimal-thresholding-based) algorithms are globally convergent to the solution of sparse optimization problems. This theoretical analysis yields an improved RIP bound for the guaranteed performance of thresholding algorithms. The numerical experiments demonstrate that the traditional hard thresholding methods have been significantly transcended by the proposed algorithms which also outperform the classic $\ell_1$-minimization method in solving sparse optimization problems.