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 f the hard thresholding pursuit (HTP) algorithm, showing that it exactly recovers the support of an arbitrary s-sparse signal within O (sκlogκ) iterations via a properly chosen proxy function, where κ is the condition number of the problem. In stark contrast to the theoretical results in th literature, the iteration complexity we obtained holds without assuming the restricted isometry property, or relaxing the sparsity, or utilizing t 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.