On the Iteration Complexity of Support Recovery via Hard Thresholding Pursuit

Jie Shen, Ping Li
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:3115-3124, 2017.

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(sklogk) 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-shen17a, title = {On the Iteration Complexity of Support Recovery via Hard Thresholding Pursuit}, author = {Jie Shen and Ping Li}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {3115--3124}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/shen17a/shen17a.pdf}, url = {https://proceedings.mlr.press/v70/shen17a.html}, 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(sklogk) 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.} }
Endnote
%0 Conference Paper %T On the Iteration Complexity of Support Recovery via Hard Thresholding Pursuit %A Jie Shen %A Ping Li %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-shen17a %I PMLR %P 3115--3124 %U https://proceedings.mlr.press/v70/shen17a.html %V 70 %X 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(sklogk) 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.
APA
Shen, J. & Li, P.. (2017). On the Iteration Complexity of Support Recovery via Hard Thresholding Pursuit. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:3115-3124 Available from https://proceedings.mlr.press/v70/shen17a.html.

Related Material