On the Iteration Complexity of Support Recovery via Hard Thresholding Pursuit
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Partial Hard Thresholding: Towards A Principled Analysis of Support Recovery
In machine learning and compressed sensing, it is of central importance to understand when a tractable algorithm recovers the support of a sparse signal from its compressed measurements. In this paper, we present a princ…
compressed sensingEfficient Stochastic Gradient Hard Thresholding
Stochastic gradient hard thresholding methods have recently been shown to work favorably in solving large-scale empirical risk minimization problems under sparsity or rank constraint. Despite the improved iteration compl…
Computational EfficiencyRobust Sparse Signal Recovery with Outliers: A Hard Thresholding Pursuit Approach Based on LAD
Recovering a sparse signal from outlier-contaminated measurements is a fundamental challenge in many applications. While existing algorithms predominantly address scenarios with bounded noise or assume known signal spars…
Provable Inductive Robust PCA via Iterative Hard Thresholding
The robust PCA problem, wherein, given an input data matrix that is the superposition of a low-rank matrix and a sparse matrix, we aim to separate out the low-rank and sparse components, is a well-studied problem in mach…
Modified Hard Thresholding Pursuit with Regularization Assisted Support Identification
Hard thresholding pursuit (HTP) is a recently proposed iterative sparse recovery algorithm which is a result of combination of a support selection step from iterated hard thresholding (IHT) and an estimation step from th…