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

Fingerprint

Computational complexity
Statistics
Recovery

All Science Journal Classification (ASJC) codes

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

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).
Shen, Jie ; Li, Ping. / On the iteration complexity of support recovery via hard thresholding pursuit. 34th International Conference on Machine Learning, ICML 2017. International Machine Learning Society (IMLS), 2017. pp. 4802-4823 (34th International Conference on Machine Learning, ICML 2017).
@inproceedings{cf30abf2179944c281b26e45e53be537,
title = "On the iteration complexity of support recovery via hard thresholding pursuit",
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 {\"O} (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.",
author = "Jie Shen and Ping Li",
year = "2017",
month = "1",
day = "1",
language = "English (US)",
series = "34th International Conference on Machine Learning, ICML 2017",
publisher = "International Machine Learning Society (IMLS)",
pages = "4802--4823",
booktitle = "34th International Conference on Machine Learning, ICML 2017",

}

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. 34th International Conference on Machine Learning, ICML 2017, vol. 7, International Machine Learning Society (IMLS), pp. 4802-4823, 34th International Conference on Machine Learning, ICML 2017, Sydney, Australia, 8/6/17.

On the iteration complexity of support recovery via hard thresholding pursuit. / Shen, Jie; Li, Ping.

34th International Conference on Machine Learning, ICML 2017. International Machine Learning Society (IMLS), 2017. p. 4802-4823 (34th International Conference on Machine Learning, ICML 2017; Vol. 7).

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

TY - GEN

T1 - On the iteration complexity of support recovery via hard thresholding pursuit

AU - Shen, Jie

AU - Li, Ping

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85048503123&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85048503123&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85048503123

T3 - 34th International Conference on Machine Learning, ICML 2017

SP - 4802

EP - 4823

BT - 34th International Conference on Machine Learning, ICML 2017

PB - International Machine Learning Society (IMLS)

ER -

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