Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
复制标题
DOI：
--
复制
发表时间：
2013-11
期刊：
影响因子：
--
通讯作者：
Xiao-Tong Yuan;Ping Li;Tong Zhang
中科院分区：
文献类型：
--
作者：
Xiao-Tong Yuan;Ping Li;Tong Zhang
HTP是一种求解欠定线性方程组稀疏解的迭代贪婪选择算法。该方法已被证明具有强大的理论保证和令人印象深刻的数值性能。在本文中，我们将HTP从压缩感知推广到稀疏约束凸优化的一般问题设置。所提出的算法迭代之间的标准梯度下降步骤和硬阈值的步骤，或没有去偏。我们证明，我们的方法享有类似于HTP的收敛速度和参数估计精度的强保证。数值实验表明，该方法在稀疏逻辑回归和稀疏精度矩阵估计任务中上级最先进的贪婪选择方法。
Hard Thresholding Pursuit (HTP) is an iterative greedy selection procedure for finding sparse solutions of underdetermined linear systems. This method has been shown to have strong theoretical guarantee and impressive numerical performance. In this paper, we generalize HTP from compressive sensing to a generic problem setup of sparsity-constrained convex optimization. The proposed algorithm iterates between a standard gradient descent step and a hard thresholding step with or without debiasing. We prove that our method enjoys the strong guarantees analogous to HTP in terms of rate of convergence and parameter estimation accuracy. Numerical evidences show that our method is superior to the state-of-the-art greedy selection methods in sparse logistic regression and sparse precision matrix estimation tasks.