基于迭代投影的梯度硬阈值追踪算法

doi:10.15960/j.cnki.issn.1007-6093.2019.01.001

运筹学学报 ›› 2019, Vol. 23 ›› Issue (1): 1-14.doi: 10.15960/j.cnki.issn.1007-6093.2019.01.001

• 运筹学 • 下一篇

基于迭代投影的梯度硬阈值追踪算法

陈薪蓓¹, 朱明康², 陈建利^1,*

1. 福州大学离散数学及其应用教育部重点实验室, 福州 350108;
2. 福州第一中学, 福州 350116

收稿日期:2017-01-24 出版日期:2019-03-15 发布日期:2019-03-15
通讯作者: 陈建利 E-mail:jlchen@fzu.edu.cn
基金资助:
国家自然科学基金（No.A11501115），福建省高校杰出青年人才培育计划（No.SX2016-21）

Iterative projection gradient hard thresholding pursuit algorithm for sparse optimization

CHEN Xinbei¹, ZHU Mingkang², CHEN Jianli^1,*

1. Key Laboratory of Discrete Mathematics with Applications Ministry of Education, Fuzhou University, Fuzhou 350108, China;
2. Fuzhou No.1 High School, Fuzhou 350116, China

Received:2017-01-24 Online:2019-03-15 Published:2019-03-15

摘要/Abstract

摘要：

梯度硬阈值追踪算法是求解稀疏优化问题的有效算法之一.考虑到算法中投影对最优解的影响，提出一种比贪婪策略更好的投影算法是很有必要的.针对一般的稀疏约束优化问题，利用整数规划提出一种迭代投影策略，将梯度投影算法中的投影作为一个子问题求解.通过迭代求解该子问题得到投影的指标集，并以此继续求解原问题，以提高梯度硬阈值追踪算法的计算效果.证明了算法的收敛性，并通过数值实例验证了算法的有效性.

关键词: 稀疏约束, 整数规划, 梯度硬阈值追踪, 迭代投影

Abstract:

The gradient hard threshold pursuit algorithm is considered as one of the most effective algorithms for solving sparse optimization problems. Since greedy projection operator affects the performance of the algorithm, it is desirable to propose a better projection algorithm besides the greedy strategies. In this paper, we first formulate the projection problem as an integer programming subproblem. Then, by iteratively solving the subproblem, we obtain a better support set of the sparse optimization problem, thus the original problem is solved to improve the performance of the gradient hard threshold pursuit algorithm. Finally, the convergence of the improved algorithm is proved, and the effectiveness of the algorithm is verified by numerical experiments.

Key words: sparsity constraint, integer program, gradient hard thresholding pursuit algorithm, iterative projection

中图分类号:

O224

陈薪蓓, 朱明康, 陈建利. 基于迭代投影的梯度硬阈值追踪算法[J]. 运筹学学报, 2019, 23(1): 1-14.

CHEN Xinbei, ZHU Mingkang, CHEN Jianli. Iterative projection gradient hard thresholding pursuit algorithm for sparse optimization[J]. Operations Research Transactions, 2019, 23(1): 1-14.

参考文献

[1] Bach F, Ahipasaoglu S D, Aspremont A. Convex relaxations for subset selection[J]. ArXiv 1006.3601, 2010.
[2] Jokar S, Pfetsch M E. Exact and approximate sparse solutions of underdetermined linear equations[J]. SIAM Journal on Scientific Computing, 2008, 31(1):23-44.
[3] Natarajan B K. Sparse approximate solutions to linear systems[J]. SIAM Journal on Computing, 1995, 24(2):227-234.
[4] Mallat S, Zhang Z. Matching pursuits with time-frequency dictionaries[J]. IEEE Transactions on Signal Processing, 1993, 41(12):3397-3415.
[5] Tropp J A, Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12):4655-4666.
[6] Needell D, Tropp J A. CoSaMP:Iterative signal recovery from incomplete and inaccurate samples[J]. Applied and Computational Harmonic Analysis, 2009, 26(3):301-321.
[7] Foucart S. Hard thresholding pursuit:An algorithm for compressive sensing[J]. SIAM Journal on Numerical Analysis, 2011, 49(6):2543-2563.
[8] Blumensath T, Davies M E. Iterative hard thresholding for compressed sensing[J]. Applied and Computational Harmonic Analysis, 2008, 27(3):265-274.
[9] Dai W, Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction[J]. IEEE Transactions on Information Theory, 2009, 55(5):2230-2249.
[10] Figueiredo M A, Nowak R, Wright S J, et al. Gradient projection for sparse reconstruction:Application to compressed sensing and other inverse problems[J]. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4):586-597.
[11] Kim S, Koh K, Lustig M, et al. An interior-point method for large-scale l₁-regularized least squares[J]. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4):606-617.
[12] Yang J, Zhang Y. Alternating direction algorithms for l₁-problems in compressive sensing[J]. SIAM Journal on Scientific Computing, 2011, 33(1):250-278.
[13] Beck A, Teboulle M. A fast iterative shrinkage thresholding algorithm for linear inverse problems[J]. SIAM Journal on Imaging Sciences, 2009, 2(1):183-202.
[14] Wright S J, Nowak R, Figueiredo M A, et al. Sparse reconstruction by separable approximation[J]. IEEE Transactions on Signal Processing, 2009, 57(7):2479-2493.
[15] Asif M S, Romberg J. Fast and accurate algorithms for re-weighted l₁-norm minimization[J]. IEEE Transactions on Signal Processing, 2013, 61(23):5905-5916.
[16] Efron B, Hastie T, Johnstone I M, et al. Least angle regression[J]. Annals of Statistics, 2004, 32(2):407-499.
[17] Xiao L, Zhang T. A proximal-gradient homotopy method for the sparse least-squares problem[J]. SIAM Journal on Optimization, 2012, 23(2):1062-1091.
[18] Langford J, Li L, Zhang T, et al. Sparse online learning via truncated gradient[J]. Journal of Machine Learning Research, 2009:777-801.
[19] Yuan X, Li P, Zhang T. Gradient hard thresholding pursuit for sparsity-constrained optimization[C]//Proceedings of the 31st International Conference on Machine Learning, Beijing:IMLS Publisher, 2014.
[20] Baes M, Pia A D, Nesterov Y, et al. Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes[J]. Mathematical Programming, 2012, 134(1):305-322.
[21] Lu Z, Zhang Y. Sparse approximation via penalty decomposition methods[J]. SIAM Journal on Optimization, 2012, 23(4):2448-2478.
[22] Bishop C M. Pattern Recognition and Machine Learning[M]. New York:Springer-Verlag, 2006.

基于迭代投影的梯度硬阈值追踪算法

Iterative projection gradient hard thresholding pursuit algorithm for sparse optimization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

本文评价

[1]	宋珊, 冯岩, 徐常青. 基于正交稀疏约束非负张量分解的人脸识别算法[J]. 运筹学学报, 2021, 25(2): 55-66.
[2]	沈吟东, 钱壮, 李媛媛. 公共交通驾驶员调度研究综述[J]. 运筹学学报, 2021, 25(1): 1-16.
[3]	赵丹, 高岳林. 非线性整数规划问题的无参数填充函数算法[J]. 运筹学学报, 2020, 24(4): 63-73.
[4]	郑宇军, 吴晨昕, 陈恩富, 卢雪琴, 张敏霞. 新冠肺炎疫情条件下的企业复工复产优化规划方法[J]. 运筹学学报, 2020, 24(3): 43-56.
[5]	杨沐明, 黄亚魁, 戴彧虹. 一类多商品设施选址问题的基于线性松弛解的启发式方法[J]. 运筹学学报, 2019, 23(3): 15-26.
[6]	朱征露, 鲁习文. 带学习效应的两台平行机时间表长问题[J]. 运筹学学报, 2018, 22(1): 55-66.
[7]	吴佩佩, 高岳林. 一个新的非线性整数规划问题的单参数填充函数算法[J]. 运筹学学报, 2017, 21(3): 111-118.
[8]	董振宇, 冯恩民, 尹洪超, 张誉铎. 国际原油价格预测的双层随机整数规划模型、算法及应用[J]. 运筹学学报, 2015, 19(3): 18-25.
[9]	何胜学. 无预警紧急疏散中公交车辆路径的确定方法[J]. 运筹学学报, 2014, 18(3): 47-59.
[10]	孙小玲，李端. 整数规划新进展[J]. 运筹学学报, 2014, 18(1): 39-68.
[11]	孙小玲, 白晓迪, 郑小金. 概率约束最优化问题[J]. 运筹学学报, 2012, 16(3): 65-74.
[12]	田静, 吴至友, J. Ugon. 一类特殊多项式整数规划问题的最优化算法[J]. 运筹学学报, 2011, 15(4): 23-35.