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 principled analysis on the support recovery performance for a family of hard thresholding algorithms. To this end, we appeal to the partial hard thresholding (PHT) operator proposed recently by Jain et al. [IEEE Trans. Information Theory, 2017]. We show that under proper conditions, PHT recovers an arbitrary "s"-sparse signal within O(s kappa log kappa) iterations where "kappa" is an appropriate condition number. Specifying the PHT operator, we obtain the best known result for hard thresholding pursuit and orthogonal matching pursuit with replacement. Experiments on the simulated data complement our theoretical findings and also illustrate the effectiveness of PHT compared to other popular recovery methods.
Code (0)
등록된 구현이 없습니다.
Tasks
compressed sensingSimilar Papers 제목 키워드 기반
On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
The use of M-estimators in generalized linear regression models in high dimensional settings requires risk minimization with hard $L_0$ constraints. Of the known methods, the class of projected gradient descent (also kno…
regressionVocal Bursts Intensity PredictionOrthogonal Matching Pursuit with Replacement
In this paper, we consider the problem of compressed sensing where the goal is to recover almost all the sparse vectors using a small number of fixed linear measurements. For this problem, we propose a novel partial hard…
compressed sensingZeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity
$\ell_0$ constrained optimization is prevalent in machine learning, particularly for high-dimensional problems, because it is a fundamental approach to achieve sparse learning. Hard-thresholding gradient descent is a dom…
Portfolio OptimizationSparse LearningStochastic OptimizationEfficient Relaxed Gradient Support Pursuit for Sparsity Constrained Non-convex Optimization
Large-scale non-convex sparsity-constrained problems have recently gained extensive attention. Most existing deterministic optimization methods (e.g., GraSP) are not suitable for large-scale and high-dimensional problems…
Stochastic OptimizationOn 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 …