稀疏优化理论与算法若干新进展

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

Abstract

Abstract: Sparse optimization is an important class of nonconvex and discountinuous optimization problems due to the involved ℓ₀ norm regularization or the sparsity constraint. It has wide applications arising in many fields including signal and image processing, machine learning, economics and statistics. Over the past ten years, sparse optimization has attracted much attention and has become a hot research topic, with an accumulation of fruitful research achievements. In order to further promote the research in this direction, we mainly summarize and review the research results in theory and in algorithms during the last five years, along with some related important references, so as to dedicate to the readers.

Key words: sparse optimization, ℓ₀ norm, sparse set, theory, algorithm, group sparsity

CLC Number:

O224

ZHAO Chen, LUO Ziyan, XIU Naihua. Some advances in theory and algorithms for sparse optimization[J]. Operations Research Transactions, 2020, 24(4): 1-24.

References

[1] Candès E J, Tao T. Decoding by linear programming[J]. IEEE Transactions on Information Theory, 2005, 51(12):4203-4215.
[2] Candès E J. Compressive sampling[C]//Proceedings of the International Congress of Mathematicians, 2006.
[3] Candès E J, Romberg J, Tao T. Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2):489-509.
[4] Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4):1289-1306.
[5] Elad M, Figueiredo M A, Ma Y. On the role of sparse and redundant representations in image processing[J]. Proceedings of the IEEE, 2010, 98(6):972-982.
[6] Blumensath T. Compressed sensing with nonlinear observations and related nonlinear optimization problems[J]. IEEE Transactions on Information Theory, 2013, 59(6):3466-3474.
[7] Chartrand R. Exact reconstruction of sparse signals via nonconvex minimization[J]. IEEE Signal Processing Letters, 2007, 14(10):707-710.
[8] Herrity K K, Gilbert A C, Tropp J A. Sparse approximation via iterative thresholding[C]//2006 IEEE International Conference on Acoustics Speech and Signal Processing Proceedings, 2006, 624-627.
[9] Wright S J, Nowak R D, Figueiredo M A. Sparse reconstruction by separable approximation[J]. IEEE Transactions on Signal Processing, 2009, 57(7):2479-2493.
[10] Boyd S, Parikh N, Chu E, et al. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[M]. Boston:Now Publishers Inc, 2011.
[11] Smola A J, Schölkopf B. Sparse greedy matrix approximation for machine learning[C]//Proceedings of the 17th International Conference on Machine Learning, 2000, 911-918.
[12] Tipping M. Sparse bayesian learning and relevance vector machine[J]. Journal of Machine Learning Research, 2001, 1:211-244.
[13] Yuan X T, Liu X B, Yan S C. Visual classification with multitask joint sparse representation[J]. IEEE Transactions on Image Processing, 2012, 21(10):4349-4360.
[14] Bishop C M. Pattern recognition[J]. Machine Learning, 2006, 128:1-58.
[15] Wright J, Ma Y, Mairal J, et al. Sparse representation for computer vision and pattern recognition[J]. Proceedings of the IEEE, 2010, 98(6):1031-1044.
[16] Pham D S, Venkatesh S. Joint learning and dictionary construction for pattern recognition[C]//IEEE Conference on Computer Vision and Pattern Recognition, 2008, 1-8.
[17] Patel V M, Chellappa R. Sparse representations, compressive sensing and dictionaries for pattern recognition[C]//First Asian Conference on Pattern Recognition, 2011, 325-329.
[18] Bienstock D. Computational study of a family of mixed-integer quadratic programming problems[J]. Mathematical Programming, 1996, 74(2):121-140.
[19] Brodie J, Daubechies I, De Mol C, et al. Sparse and stable Markowitz portfolios[J]. Proceedings of the National Academy of Sciences, 2009, 106(30):12267-12272.
[20] Gao J J, Li D. Optimal cardinality constrained portfolio selection[J]. Operation Research, 2013, 61(3):745-761.
[21] Xu F M, Lu Z S, Xu Z B. An efficient optimization approach for a cardinality-constrained index tracking problem[J]. Optimization Methods and Software, 2016, 31:258-271.
[22] Li D, Sun X L, Wang J. Optimal lot solution to cardinality constrained mean-variance formulation for portfolio selection[J]. Mathematical Finance, 2006, 16(1):83-101.
[23] Zhao Z H, Xu F M, Li X Y. Adaptive projected gradient thresholding methods for constrained ℓ₀ problems[J]. Science China Mathematics, 2015, 58(10):1-20.
[24] Kim S J, Koh K, Lustig M, Boyd S, Gorinevsky D. An interior-point method for large-scale ℓ₁-regularized least squares[J]. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4):606-617.
[25] Liu J, Chen J H, Ye J P. Large-scale sparse logistic regression[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009.
[26] Bunea F. Honest variable selection in linear and logistic regression models via ℓ₁ and l₁+ l₂ penalization[J]. Electronic Journal of Statistics, 2008, 2:1153-1194.
[27] Misra J. Interactive exploration of microarray gene expression patterns in a reduced dimensional space[J]. Genome Research, 2002, 12(7):1112-1120.
[28] Beck A, Vaisbourd Y. The sparse principal component analysis problem:Optimality conditions and algorithms[J]. Journal of Optimization Theory and Applications, 2016, 170(1):119-143.
[29] Zou H, Hastie T, Tibshirani R. Sparse principal component analysis[J]. Journal of Computational and Graphical Statistics, 2006, 15(2):265-286.
[30] Candès E J, Wakin M B. An introduction to compressive sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2):21-30.
[31] Bahmani S, Boufounos P T, Raj B. Learning model-based sparsity via projected gradient descent[J]. IEEE Transactions on Information Theory, 2016, 62(4):2092-2099.
[32] Agarwal A, Negahban S, Wainwright M J. Fast global convergence rates of gradient methods for high-dimensional statistical recovery[C]//Advances in Neural Information Processing Systems, 2010, 37-45.
[33] Negahban S N, Ravikumar P, Wainwright M J, et al. A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers[J]. Statistical Science, 2012, 27(4):538-557.
[34] Natarajan B K. Sparse approximate solutions to linear systems[J]. SIAM Journal on Computing, 1995, 24(2):227-234.
[35] 文再文, 印卧涛, 刘歆, 等. 压缩感知和稀疏优化简介[J]. 运筹学学报, 2012, 16(3):49-64.
[36] 许志强. 压缩感知[J]. 中国科学, 2012, 42(9):865-877.
[37] 马坚伟, 徐杰, 鲍跃全, 等. 压缩感知及其应用:从稀疏约束到低秩约束优化[J]. 信号处理, 2012,28(5):609-623.
[38] 秦林霞. 非负稀疏优化的精确松弛理论研究[D]. 北京:北京交通大学, 2013.
[39] 于春梅. 稀疏优化算法综述[J]. 计算机工程与应用, 2014, 50(11):210-217.
[40] Tropp J A, Wright S J. Computational methods for sparse solution of linear inverse problems[J]. Proceedings of the IEEE, 2010, 98(6):948-958.
[41] Foucart S, Rauhut H. A Mathematical Introduction to Compressive Sensing[M]. Boston:Birkhäuser Basel, 2013.
[42] Eldar Y C, Kutyniok G. Compressed Sensing:Theory and Applications[M]. Cambridge:Cambridge University Press, 2012.
[43] Zhao Y B. Sparse Optimization Theory and Methods[M]. Florida:CRC Press, 2018.
[44] Rockafellar R T, Wets R J. Variational Analysis[M]. New York:Springer, 1998.
[45] Clarke F H. Optimization and Nonsmooth Analysis[M]. Hoboken:Wiley, 1983.
[46] Clarke F H. Method of Dynamic and Nonsmooth Optimization[M]. Philadelphia:SIAM, 1989.
[47] Bazaraa M S, Goode J, Nashed M Z. On the cones of tangents with applications to mathematical programming[J]. Journal of Optimization Theory and Applications, 1974, 13(4):389-426.
[48] Clarke F H. Necessary conditions for nonsmooth variational problems[C]//Optimal Control Theory and its Applications, 1974, 70-91.
[49] Clarke F H. Generalized gradients and applications[J]. Transactions of the American Mathematical Society, 1975, 205:247-262.
[50] Mordukhovich B. Maximum principle in the problem of time optimal response with nonsmooth constraints[J]. Journal of Applied Mathematics and Mechanics, 1976, 40(6):960-969.
[51] Bonnans J F, Shapiro A. Perturbation Analysis of Optimization Problems[M]. New York:Springer, 2000.
[52] Le H Y. Generalized subdifferentials of the rank function[J]. Optimization Letters, 2013, 7(4):731-743.
[53] Blumensath T, Davies M E. Iterative thresholding for sparse approximations[J]. Journal of Fourier Analysis and Applications, 2008, 14(5):629-654.
[54] Blumensath T, Davies M. Iterative hard thresholding for compressed sensing[J]. Applied and Computational Harmonic Analysis, 2009, 27:265-274.
[55] Bauschke H H, Luke D R, Phan H M, et al. Restricted normal cones and sparsity optimization with affine constraints[J]. Foundations of Computational Mathematics, 2014, 14(1):63-83.
[56] Pan L L, Xiu N H, Zhou S L. On solutions of sparsity constrained optimization[J]. Journal of the Operations Research Society of China, 2015, 3(4):421-439.
[57] Pan L L, Luo Z Y, Xiu N H. Restricted Robinson constraint qualification and optimality for cardinality-constrained cone programming[J]. Journal of Optimization Theory and Applications, 2017, 175(1):104-118.
[58] Chen S S, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit[J]. SIAM Review, 2001, 43(1):129-159.
[59] Candès E J, Romberg J. ℓ₁-magic:Recovery of sparse signals via convex programming[J/OL].[2020-07-21]. http://www.acm.caltech.edu/l1magic/downloads/l1magic.pdf, 2005.
[60] Van Den Berg E, Friedlander M P. Probing the Pareto frontier for basis pursuit solutions[J]. SIAM Journal on Scientific Computing, 2008, 31(2):890-912.
[61] Tibshirani R. Regression shrinkage and selection via the lasso[J]. Journal of the Royal Statistical Society. Series B (Methodological), 1996, 58(1):267-288.
[62] Zou H. The adaptive lasso and its oracle properties[J]. Journal of the American Statistical Association, 2006, 101(476):1418-1429.
[63] Zou H, Hastie T. Regularization and variable selection via the elastic net[J]. Journal of the Royal Statistical Society:Series B (Statistical Methodology), 2005, 67:301-320.
[64] Cai T T, Zhang A. Sparse representation of a polytope and recovery of sparse signals and low-rank matrices[J]. IEEE Transactions on Information Theory, 2014, 60(1):122-132.
[65] Donoho D L, Huo X. Uncertainty principles and ideal atomic decomposition[J]. IEEE Transactions on Information Theory, 2001, 47(7):2845-2862.
[66] Mallat S G, Zhang Z. Matching pursuits with time-frequency dictionaries[J]. IEEE Transactions on Signal Processing, 1993, 41(12):3397-3415.
[67] Donoho D L, Elad M. Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ₁ minimization[J]. Proceedings of the National Academy of Sciences, 2003, 100(5):2197-2202.
[68] Juditsky A, Nemirovski A. On verifiable sufficient conditions for sparse signal recovery via ℓ₁ minimization[J]. Mathematical Programming, 2011, 127(1):57-88.
[69] Zhang Y. Theory of compressive sensing via ℓ₁-minimization:A non-RIP analysis and extensions[J]. Journal of the Operations Research Society of China, 2013, 1(1):79-105.
[70] Zhao Y B. RSP-Based analysis for sparsest and least ℓ₁-norm solutions to underdetermined linear systems[J]. IEEE Transactions on Signal Processing, 2013, 61(22):5777-5788.
[71] Luo Z Y, Qin L X, Kong L C, et al. The nonnegative zero-norm minimization under generalized z-matrix measurement[J]. Journal of Optimization Theory and Applications, 2014, 160(3):854-864.
[72] Kong L C, Sun J, Tao J Y, et al. Sparse recovery on Euclidean Jordan algebras[J]. Linear Algebra and its Applications, 2015, 465:65-87.
[73] Candès E J, Romberg J K, Tao T. Stable signal recovery from incomplete and inaccurate measurements[J]. Communications on Pure and Applied Mathematics, 2006, 59(8):1207-1223.
[74] Khoramian S. An iterative thresholding algorithm for linear inverse problems with multiconstraints and its applications[J]. Applied and Computational Harmonic Analysis, 2012, 32(1):109-130.
[75] Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM Journal on Imaging Sciences, 2009, 2:183-202.
[76] Wen Z, Yin W, Goldfarb D, et al. A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation[J]. SIAM Journal on Scientific Computing, 2010, 32(4):1832-1857.
[77] 何炳生. 凸优化和单调变分不等式收缩算法的统一框架[J]. 中国科学:数学, 2018, 48(2):255-272.
[78] He B S, Ma F, Yuan X M. Optimal proximal augmented Lagrangian method and its application to full Jacobian splitting for multi-block separable convex minimization problems[J]. IMA Journal of Numerical Analysis, 2019, 40(2):1188-1216.
[79] He B S, Ma F, Yuan X M. Optimally linearizing the alternating direction method of multipliers for convex programming[J]. Computational Optimization and Applications, 2020, 75:361-388.
[80] He B S, Tao M, Yuan X M. Convergence rate and iteration complexity on the alternating direction method of multipliers with a substitution procedure for separable convex programming[J]. Mathematics of Operations Research, 2017, 42(3):662-691.
[81] Yang J F. Compressive sensing and ℓ₁-norm decoding by ADMM[J]. Science Focus, 2016, 11(6):47-51.
[82] Yang J, Zhang Y. Alternating direction algorithms for ℓ₁-problems in compressive sensing[J]. SIAM Journal on Science Computing, 2011, 33(1):250-278.
[83] Li M, Sun D F, Toh K C. A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block[J]. Asia-Pacific Journal of Operational Research, 2015, 32(3):1550024.
[84] Cui Y, Li X D, Sun D F, et al. On the convergence properties of a majorized ADMM for linearly constrained convex optimization problems with coupled objective functions[J]. Journal of Optimization Theory and Applications, 2016, 169:1013-1041.
[85] Li M, Sun D F, Toh K C. A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization[J]. SIAM Journal on Optimization, 2016, 26(2):922-950.
[86] Han D R, Sun D F, Zhang L W. Linear rate convergence of the alternating direction method of multipliers for convex composite quadratic and semi-definite programming[J]. Mathematics of Operations Research, 2015, 43(2):622-637.
[87] Li X D, Sun D F, Toh K C. A highly efficient semismooth Newton augmented lagrangian method for solving lasso problems[J]. SIAM Journal on Optimization, 2016, 28(1):433-458.
[88] Li X D, Sun D F, Toh K C. On efficiently solving the subproblems of a level-set method for fused lasso problems[J]. SIAM Journal on Optimization, 2018, 28(2):1842-1866.
[89] Zass R, Shashua A. Nonnegative sparse PCA[J]. Advances in Neural Information Processing Systems, 2007, 19:1561.
[90] Donoho D L, Tsaig Y. Fast solution of ℓ₁-norm minimization problems when the solution may be sparse[J]. IEEE Transactions on Information Theory, 2008, 54(11):4789-4812.
[91] Van de Geer S A. High-dimensional generalized linear models and the lasso[J]. The Annals of Statistics, 2008, 26(2):614-645.
[92] Kakade S, Shamir O, Sindharan K, et al. Learning exponential families in high-dimensions:Strong convexity and sparsity[C]//AISTATS, 2010, 381-388.
[93] Zhang Y, d.Aspremont A, El Ghaoui L. Sparse PCA:Convex relaxations, algorithms and applications[M]//Handbook on Semidefinite, Conic and Polynomial Optimization, New York:Springer, 2012, 915-940.
[94] Foucart S, Lai M J. Sparsest solutions of underdetermined linear systems via lq-minimization for 0< q ≤ 1[J]. Applied and Computational Harmonic Analysis, 2009, 26(3):395-407.
[95] Chartrand R, Staneva V. Restricted isometry properties and nonconvex compressive sensing[J]. Inverse Problems, 2008, 24(3):035020.
[96] Fung G M, Mangasarian O L. Equivalence of minimal ℓ₀ and ℓ_p-norm solutions of linear equalities, inequalities and linear programs for sufficiently small p[J]. Journal of Optimization Theory and Applications, 2011, 151(1):1-10.
[97] Fan J, Kong L C, Wang L Q, et al. Variable selection in sparse regression with quadratic measurements[J]. Statistica Sinica, 2018, 28:1157-1178.
[98] Xu Z B, Chang X Y, Xu F M, et al. ℓ_1/2 regularization:A thresholding representation theory and a fast solver[J]. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(7):1013-1027.
[99] Zeng J S, Lin S B, Wang Y, et l. ℓ_1/2 regularization:Convergence of iterative half thresholding algorithm[J]. IEEE Transactions on Signal Processing, 2014, 62(9):2317-2329.
[100] Chen X J, Xu F M, Ye Y Y. Lower bound theory of nonzero entries in solutions of ℓ₂-ℓ_p minimization[J]. SIAM Journal on Scientific Computing, 2010, 32(5):2832-2852.
[101] Chen X J, Niu L F, Yuan Y X. Optimality conditions and a smoothing trust region Newton method for nonLipschitz optimization[J]. SIAM Journal on Optimization, 2013, 23(3):1528-1552.
[102] Chen X J, Guo L, Lu Z S, et al. An augmented lagrangian method for non-Lipschitz nonconvex programming[J]. SIAM Journal on Numerical Analysis, 2017, 55(1):168-193.
[103] Bian W, Chen X J, Ye Y Y. Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization[J]. Mathematical Programming, 2015, 149:301-327.
[104] Zhang C, Chen X J. A smoothing active set method for linearly constrained non-Lipschitz nonconvex optimization[J]. SIAM Journal on Optimization, 2020, 30(1):1-30.
[105] Nikolova M, Ng M K, Zhang S, et al. Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization[J]. SIAM journal on Imaging Sciences, 2008, 1(1):2-25.
[106] Fan J, Li R. Variable selection via nonconcave penalized likelihood and its oracle properties[J]. Journal of the American statistical Association, 2001, 96(456):1348-1360.
[107] Huang J, Ma S G, Xie H L, et al. A group bridge approach for variable selection[J]. Biometrika, 2009, 96(2):339-355.
[108] Zhang C H. Nearly unbiased variable selection under minimax concave penalty[J]. The Annals of Statistics, 2010, 38(2):894-942.
[109] Zhang T. Analysis of multi-stage convex relaxation for sparse regularization[J]. Journal of Machine Learning Research, 2010, 11(35):1081-1107.
[110] Ong C S, An L T H. Learning sparse classifiers with difference of convex functions algorithms[J]. Optimization Methods and Software, 2013, 28(4):830-854.
[111] Li H, Lin Z. Accelerated proximal gradient methods for nonconvex programming[J]. Nips, 2015,1:379-387.
[112] Kurdyka K. On gradients of functions definable in o-minimal structures[J]. Annales de l'Institut Fourier, 1998, 48(3):769-783.
[113] Bian W, Chen X J. A smoothing proximal gradient algorithm for nonsmooth convex regression with cardinality penalty[J]. SIAM Journal on Numerical Analysis, 2020, 58(1):858-883.
[114] Soubies E, Blanc-Féraud L, Aubert G. A continuous exact ℓ₀ penalty (CEL0) for least squares regularized problem[J]. SIAM Journal on Imaging Sciences, 2015, 8(3):1607-1639.
[115] Thi H A L, Le H M, Nguyen V V, et al. A DC programming approach for feature selection in support vector machines learning[J]. Advances in Data Analysis and Classification, 2008, 2(3):259-278.
[116] Gasso G, Rakotomamonjy A, Canu S. Recovering sparse signals with a certain family of nonconvex penalties and dc programming[J]. IEEE Transactions on Signal Processing, 2009, 57(12):4686-4698.
[117] Thi H A L, Le H M, Tao P D. Feature selection in machine learning:an exact penalty approach using a difference of convex function algorithm[J]. Machine Learning, 2015, 101(1-3):163-186.
[118] Le Thi H, Pham Dinh T, Le H, et al. Dc approximation approaches for sparse optimization[J]. European Journal of Operational Research, 2015, 244(1):26-46.
[119] Lu Z, Zhang Y. Sparse approximation via penalty decomposition methods[J]. SIAM Journal on Optimization, 2013, 23(4):2448-2478.
[120] Robinson S M. Stability theory for systems of inequalities, Part II:Differentiable nonlinear systems[J]. SIAM Journal on Numerical Analysis, 1976, 13(4):497-513.
[121] Beck A, Hallak N. On the minimization over sparse symmetric sets:projections, optimality conditions, and algorithms[J]. Mathematics of Operations Research, 2016, 41(1):196-223.
[122] Beck A, Hallak N. Proximal mapping for symmetric penalty and sparsity[J]. SIAM Journal on Optimization, 2018, 28(1):496-527.
[123] Zhou S, Pan L, Xiu N. Subspace newton method for the ℓ₀-regularized optimization[J]. arXiv:2004.05132, 2020.
[124] Zhang H, Pan L L, Xiu N H. Optimality conditions for locally Lipschitz optimization with ℓ₀-regularization[J]. Optimization Letters, 2020.
[125] Guo L, Ye J J. Necessary optimality conditions and exact penalization for non-Lipschitz nonlinear programs[J]. Mathematical Programming, 2018, 168(1):571-598.
[126] Davis G, Mallat S, Avellaneda M. Adaptive greedy approximations[J]. Constructive Approximation, 1997, 13(1):57-98.
[127] Dai W, Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction[J]. IEEE transactions on Information Theory, 2009, 55(5):2230-2249.
[128] Blanchard J D, Tanner J, Wei K. CGIHT:conjugate gradient iterative hard thresholding for compressed sensing and matrix completion[J]. Information and Inference, 2015, 4(4):289-327.
[129] Bao C, Dong B, Hou L, et al. Image restoration by minimizing zero norm of wavelet frame coefficients[J]. Inverse Problems, 2016, 32(11):115004.
[130] Lu Z. Iterative hard thresholding methods for ℓ₀ regularized convex cone programming[J]. Mathematical Programming, 2014, 147(1):125-154.
[131] Cheng W Y, Chen Z X, Hu Q J. An active set Barzilar-Borwein algorithm for ℓ₀ regularized optimization[J]. Journal of Global Optimization, 2020, 76(4):769-791.
[132] Soussen C, Idier J, Duan J, et al. Homotopy based algorithms for ℓ₀-regularized least-squares[J]. IEEE Transactions on Signal Processing, 2015, 63(13):3301-3316.
[133] Ito K, Kunisch K. A variational approach to sparsity optimization based on lagrange multiplier theory[J]. Inverse Problems, 2013, 30(1):015001.
[134] Jiao Y, Jin B, Lu X. A primal dual active set with continuation algorithm for the ℓ₀-regularized optimization problem[J]. Applied and Computational Harmonic Analysis, 2015, 39(3):400-426.
[135] Huang J, Jiao Y L, Liu Y Y, et al. A constructive approach to ℓ₀ penalized regression[J]. Journal of Machine Learning Research, 2018, 19:1-37.
[136] Nikolova M. Description of the minimizers of least squares regularized with ℓ₀-norm. uniqueness of the global minimizer[J]. SIAM Journal on Imaging Sciences, 2013, 6(2):904-937.
[137] Nikolova M. Relationship between the optimal solutions of least squares regularized with ℓ₀-norm and constrained by k-sparsity[J]. Applied and Computational Harmonic Analysis, 2016, 41(1):237-265.
[138] Shen X, Pan W, Zhu Y, et al. On constrained and regularized high-dimensional regression[J]. Annals of the Institute of Statistical Mathematics, 2013, 65(5):807-832.
[139] Chen X J, Pan L L, Xiu N H. Solution sets of three sparse optimization problems for multivariate regression[R]. Hong Kong:Hong Kong Polytechnic University, 2018.
[140] Bertsimas D, Shioda R. Algorithm for cardinality-constrained quadratic optimization[J]. Computational Optimization and Applications, 2009, 43(1):1-22.
[141] Bertsimas D, King A, Mazumder R. Best subset selection via a modern optimization lens[J]. The Annals of Statistics, 2015, 44(2):813-852.
[142] Gotoh J y, Takeda A, Tono K. DC formulations and algorithms for sparse optimization problems[J]. Mathematical Programming, 2018, 169(1):141-176.
[143] 潘丽丽. 稀疏约束优化的最优性理论与算法[D]. 北京:北京交通大学, 2017.
[144] Beck A, Eldar Y C. Sparsity constrained nonlinear optimization:Optimality conditions and algorithms[J]. SIAM Journal on Optimization, 2013, 23(3):1480-1509.
[145] Lu Z S. Optimization over sparse symmetric sets via a nonmonotone projected gradient method[J]. arXiv:1509.08581, 2015.
[146] Lu Z, Zhang Y. Sparse approximation via penalty decomposition methods[J]. SIAM Journal on Optimization, 2013, 23(4):2448-2478.
[147] Pan L L, Xiu N H, Fan J. Optimality conditions for sparse nonlinear programming[J]. Science China Mathematics, 2017, 60(5):759-776.
[148] Zhao C, Luo Z Y, Li W Y, et al. Lagrangian duality and saddle points for sparse linear programming[J]. Science China Mathematics, 2019, 62(10):2015-2032.
[149] Zhao C, Xiu N H, Qi H D, et al. A Lagrange-Newton algorithm for sparse nonlinear programming[J]. arXiv:2004.13257, 2020.
[150] Figueiredo M A T, Nowak R D, Wright S J. 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.
[151] 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.
[152] Elad M. Sparse and Redundant Representations:From Theory to Applications in Signal and Image Processing[M]. New York:Springer, 2010.
[153] Bahmani S, Raj B, Boufounos P T. Greedy sparsity-constrained optimization[J]. Journal of Machine Learning Research, 2013, 14:807-841.
[154] Kyrillidis A, Cevher V. Recipes on hard thresholding methods[C]//4th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2011, 353-356.
[155] Blumensath T, Davies M E. Normalized iterative hard thresholding:Guaranteed stability and performance[J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2):298-309.
[156] Blumensath T. Accelerated iterative hard thresholding[J]. Signal Processing, 2012, 92(3):752-756.
[157] Foucart S. Hard thresholding pursuit:an algorithm for compressive sensing[J]. SIAM Journal on Numerical Analysis, 2011, 49(6):2543-2563.
[158] Zhou S L, Xiu N H, Qi H D. Global and quadratic convergence of Newton hard-thresholding pursuit[J]. arXiv:1901.02763, 2019.
[159] Yuan X T, Li P, Zhang T. Gradient hard thresholding pursuit[J]. Journal of Machine Learning Research, 2018, 18:1-43.
[160] Wang R, Xiu N H, Zhang C. Greedy projected gradient-newton method for sparse logistic regression[J]. IEEE Transactions on Neural Networks and Learning Systems, 2020, 31(2):527-538.
[161] Jenatton R, Audibert J Y, Bach F. Structured variable selection with sparsity-inducing norms[J]. Journal of Machine Learning Research, 2009, 12:2777-2824.
[162] 刘建伟, 崔立鹏, 罗雄麟. 组稀疏模型及其算法综述[J]. 电子学报, 2015, 43(004):776-782.
[163] Meier L, van de Geer S, Bjhlmann P. The group lasso for logistic regression[J]. Journal of the Royal Statal Society:Series B (Statal Methodology), 2008, 70(1):53-71.
[164] Lin Y Y. Model selection and estimation in regression with grouped variables[J]. Journal of the Royal Statistical Society, 2006, 68(1):49-67.
[165] Bogdan M, van den Berg E, Sabatti C, et al. SLOPE-Adaptive variable selection via convex optimization[J]. Annals of Applied Statistics, 2015, 9(3):1103-1140.
[166] Eldar Y, Mishali M. Robust recovery of signals from a structured union of subspaces[J]. IEEE Transactions on Information Theory, 2009, 55(11):5302-5316.
[167] Stojnic M, Parvaresh F, Hassibi B. On the reconstruction of block-sparse signals with an optimal number of measurements[J]. IEEE Transactions on Signal Processing, 2009, 57(8).
[168] Baraniuk R G, Cevher V, Duarte M F, et al. Model-based compressive sensing[J]. IEEE Transactions on Information Theory, 2010, 56(4):1982-2001.
[169] Blumensath T, Davies M E. Sampling theorems for signals from the union of finite-dimensional linear subspaces[J]. IEEE Transactions on Information Theory, 2009, 55(4):1872-1882.
[170] Eldar Y C, Kuppinger P, Bolcskei H. Block-sparse signals:Uncertainty relations and efficient recovery[J]. IEEE Transactions on Signal Processing, 2010, 58(6):3042-3054.
[171] Duarte M F, Cevher V, Baraniuk R G. Model-based compressive sensing for signal ensembles[C]//2009 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2010.
[172] Duarte M F, Eldar Y C. Structured compressed sensing:From theory to applications[J]. IEEE Transactions on Signal Processing, 2011, 59(9):4053-4085.
[173] Baldassarre L, Bhan N, Cevher V, et al. Group-sparse model selection:Hardness and relaxations[J]. IEEE Transactions on Information Theory, 2016, 62(11).
[174] Jain P, Rao N, Dhillon I. Structured sparse regression via greedy hard-thresholding[J]. arXiv:1602.06042, 2016.
[175] Pan L L, Chen X J. Group sparse optimization for images recovery using capped folded concave functions[J]. SIAM Journal on Imaging Sciences, 2020.
[176] Zhang Y J, Zhang N, Sun D F, et al. A proximal point dual Newton algorithm for solving group graphical lasso problems[J]. SIAM Journal on Optimization, 2020, 30(3):2197-2220.
[177] Zhang Y J, Zhang N, Sun D F, et al. An efficient hessian based algorithm for solving large-scale sparse group lasso problems[J]. Mathematical Programming, 2020, 179:223-263.
[178] Peng D T, Chen X J. Computation of second-order directional stationary points for group sparse optimization[J]. Optimization Methods and Software, 2020, 35:348-376.
[179] Luo Z Y, Sun D F, Toh K C, et al. Solving the OSCAR and SLOPE models using a semismooth newton-based augmented lagrangian method[J]. Journal of Machine Learning Research, 2019, 20(106):1-25.
[180] Chen X J, Toint P L. High-order evaluation complexity for convexly-constrained optimization with non-Lipschitzian group sparsity terms[J]. Mathematical Programming, 2020.
[181] Beck A, Hallak N. Optimization problems involving group sparsity terms[J]. Mathematical Programming, 2019, 178:39-67.

Some advances in theory and algorithms for sparse optimization

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	HUANG Zhipeng, LI Xingquan, ZHU Wenxing. Optimization models and algorithms for placement of very large scale integrated circuits [J]. Operations Research Transactions, 2021, 25(3): 15-36.
[2]	XU Zi, ZHANG Huiling. Optimization algorithms and their complexity analysis for non-convex minimax problems [J]. Operations Research Transactions, 2021, 25(3): 74-86.
[3]	ZHOU Yuyang, ZHANG Huizhen, MA Liang. An improved immune algorithm for solving hierarchical and progressive location problem of emergency medical facilities [J]. Operations Research Transactions, 2021, 25(2): 15-34.
[4]	QIAN Xiaohui, WANG Xiangmei. A scaled incremental gradient method [J]. Operations Research Transactions, 2021, 25(2): 81-92.
[5]	ZHOU Xueling, LI Meixia, CHE Haitao. Successive relaxed projection algorithm for multiple-sets split equality problem [J]. Operations Research Transactions, 2021, 25(2): 93-103.
[6]	QU Biao, XU Wei, WANG Xinyan. A remark on the convergence of the two-subgradient extragradient algorithm for the variational inequality problem [J]. Operations Research Transactions, 2021, 25(2): 144-148.
[7]	YU Hai, ZHAN Wanrong. Strongly convergent ball-relaxed CQ algorithm and its application [J]. Operations Research Transactions, 2021, 25(1): 50-60.
[8]	QU Deqiang, SHANG Youlin, ZHAN Yue, WU Dan. A new parameterless filled function for global optimization problems [J]. Operations Research Transactions, 2021, 25(1): 89-95.
[9]	BAO Xiaoguang, LU Chao, HUANG Dongmei, YU Wei. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113.
[10]	REN Jianfeng, TIAN Xiaoyun. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[11]	GUO Xiaoling, ZHUANG Yuanxin, LIU Yifan. Research on the quadratic programming model and solution algorithm of critical nodes in metro network [J]. Operations Research Transactions, 2020, 24(4): 51-62.
[12]	HUANG Jidan, ZHENG Feifeng, XU Yingfeng, LIU Ming. Parallel machine scheduling with deteriorating installation times in the MapReduce system [J]. Operations Research Transactions, 2020, 24(4): 93-106.
[13]	LU Shuxiang, Lü Changhong, QIN Tao. An algorithm based on makespan lower bound for quay crane schedule problem in container terminals [J]. Operations Research Transactions, 2020, 24(3): 67-76.
[14]	YANG Linxi, LI Guoquan. Sparse proximal support vector machines via DC programming [J]. Operations Research Transactions, 2020, 24(3): 115-126.
[15]	HE Asi, ZHANG Shenggui. A new modified SR1 update formulas and its algorithm convergence [J]. Operations Research Transactions, 2020, 24(3): 141-153.