TY - GEN
T1 - On the iteration complexity of support recovery via hard thresholding pursuit
AU - Shen, Jie
AU - Li, Ping
N1 - Publisher Copyright:
Copyright © 2017 by the authors.
PY - 2017
Y1 - 2017
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
T2 - 34th International Conference on Machine Learning, ICML 2017
Y2 - 6 August 2017 through 11 August 2017
ER -