On the iteration complexity of support recovery via hard thresholding pursuit

Jie Shen, Ping Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Recovering the support of a sparse signal from its compressed samples has been one of the most important problems in high dimensional statistics. In this paper, we present a novel analysis for the hard thresholding pursuit (HTP) algorithm, showing that it exactly recovers the support of an arbitrary s-sparse signal within Ö (s log K) iterations via a properly chosen proxy function, where K is the condition number of the problem. In stark contrast to the theoretical results in the literature, the iteration complexity we obtained holds without assuming the restricted isometry property, or relaxing the sparsity, or utilizing the optimality of the underlying signal. We further extend our result to a more challenging scenario, where the subproblem involved in HTP cannot be solved exactly. We prove that even in this setting, support recovery is possible and the computational complexity of HTP is established. Numerical study substantiates our theoretical results.

Original languageEnglish (US)
Title of host publication34th International Conference on Machine Learning, ICML 2017
PublisherInternational Machine Learning Society (IMLS)
Pages4802-4823
Number of pages22
ISBN (Electronic)9781510855144
StatePublished - Jan 1 2017
Event34th International Conference on Machine Learning, ICML 2017 - Sydney, Australia
Duration: Aug 6 2017Aug 11 2017

Publication series

Name34th International Conference on Machine Learning, ICML 2017
Volume7

Other

Other34th International Conference on Machine Learning, ICML 2017
CountryAustralia
CitySydney
Period8/6/178/11/17

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Human-Computer Interaction
  • Software

Fingerprint Dive into the research topics of 'On the iteration complexity of support recovery via hard thresholding pursuit'. Together they form a unique fingerprint.

  • Cite this

    Shen, J., & Li, P. (2017). On the iteration complexity of support recovery via hard thresholding pursuit. In 34th International Conference on Machine Learning, ICML 2017 (pp. 4802-4823). (34th International Conference on Machine Learning, ICML 2017; Vol. 7). International Machine Learning Society (IMLS).