Optimal k-thresholding algorithms for sparse optimization problems

Yun-Bin Zhao

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)
213 Downloads (Pure)


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.
Original languageEnglish
Article number25
Pages (from-to)31-55
JournalSIAM Journal on Optimization
Issue number1
Publication statusPublished - 2 Jan 2020


  • Convex optimization
  • Hard thresholding
  • Iterative algorithms
  • Optimal k-thresholding
  • Restricted isometry property
  • Sparse optimization

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science


Dive into the research topics of 'Optimal k-thresholding algorithms for sparse optimization problems'. Together they form a unique fingerprint.

Cite this