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

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

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

CLC Number:

O224

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.

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 9

Recommended Articles

Metrics

Comments

[1]	ZHAO Dan, GAO Yuelin. Non-parameter filled function method for nonlinear integer programming [J]. Operations Research Transactions, 2020, 24(4): 63-73.
[2]	ZHENG Yujun, WU Chenxin, CHEN Enfu, LU Xueqin, ZHANG Minxia. An optimization method for production resumption planning under COVID-19 Epidemic [J]. Operations Research Transactions, 2020, 24(3): 43-56.
[3]	YANG Muming, HUANG Yakui, DAI Yuhong. Linear relaxation solution based heuristics for a class of multi-product facility location problems [J]. Operations Research Transactions, 2019, 23(3): 15-26.
[4]	ZHU Zhenglu, LU Xiwen. Minimizing makespan on two parallel machines with learning effects [J]. Operations Research Transactions, 2018, 22(1): 55-66.
[5]	WU Peipei, GAO Yuelin. A new single parameter filled function method for nonlinear integer programming [J]. Operations Research Transactions, 2017, 21(3): 111-118.
[6]	DONG Zhenyu, FENG Enmin, YIN Hongchao, ZHANG Yuduo. International crude prices forecast of double random integer programming model,algorithm and application [J]. Operations Research Transactions, 2015, 19(3): 18-25.
[7]	SUN Xiaoling, LI Duan. Recent advances in integer programming [J]. Operations Research Transactions, 2014, 18(1): 39-68.
[8]	SUN Xiaoling, BAI Xiaodi, ZHENG Xiaojin. A survey on probabilistically constrained optimization problems [J]. Operations Research Transactions, 2012, 16(3): 65-74.
[9]	TIAN Jing, WU Zhi-You, J. Ugon. Optimization Methods for a Class of Integer Polynomial Programming Problems [J]. Operations Research Transactions, 2011, 15(4): 23-35.