Gradient hard thresholding pursuit

Xiao Tong Yuan, Ping Li, Tong Zhang

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

Hard Thresholding Pursuit (HTP) is an iterative greedy selection procedure for finding sparse solutions of underdetermined linear systems. This method has been shown to have strong theoretical guarantee and impressive numerical performance. In this article, we generalize HTP from compressed sensing to a generic problem setup of sparsity-constrained convex optimization. The proposed algorithm iterates between a standard gradient descent step and a hard-thresholding step with or without debiasing. We analyze the parameter estimation and sparsity recovery performance of the proposed method. Extensive numerical results confirm our theoretical predictions and demonstrate the superiority of our method to the state-of-the-art greedy selection methods in sparse linear regression, sparse logistic regression and sparse precision matrix estimation problems.

Original languageEnglish (US)
Pages (from-to)1-43
Number of pages43
JournalJournal of Machine Learning Research
Volume18
StatePublished - May 1 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Keywords

  • Greedy Selection
  • Hard Thresholding Pursuit
  • Sparsity Recovery

Fingerprint

Dive into the research topics of 'Gradient hard thresholding pursuit'. Together they form a unique fingerprint.

Cite this