# American Institute of Mathematical Sciences

February  2022, 16(1): 153-177. doi: 10.3934/ipi.2021044

## Smoothing Newton method for $\ell^0$-$\ell^2$ regularized linear inverse problem

 1 School of Statistics, Key Laboratory of Advanced Theory and Application, in Statistics and Data Science-MOE, East China Normal University, Shanghai 200062, China 2 School of Mathematics and Statistics, and Hubei Key Laboratory of Computational Science, , Wuhan University, Wuhan 430072, China 3 School of Mathematics and Statistics, Henan University, Kaifeng 475000, China

Received  September 2020 Revised  May 2021 Published  February 2022 Early access  July 2021

Sparse regression plays a very important role in statistics, machine learning, image and signal processing. In this paper, we consider a high-dimensional linear inverse problem with $\ell^0$-$\ell^2$ penalty to stably reconstruct the sparse signals. Based on the sufficient and necessary condition of the coordinate-wise minimizers, we design a smoothing Newton method with continuation strategy on the regularization parameter. We prove the global convergence of the proposed algorithm. Several numerical examples are provided, and the comparisons with the state-of-the-art algorithms verify the effectiveness and superiority of the proposed method.

Citation: Peili Li, Xiliang Lu, Yunhai Xiao. Smoothing Newton method for $\ell^0$-$\ell^2$ regularized linear inverse problem. Inverse Problems & Imaging, 2022, 16 (1) : 153-177. doi: 10.3934/ipi.2021044
##### References:
 [1] H. Akaike, A new look at the statistical model identification, IEEE Transactions on Automatic Control, 19 (1974), 716-723.  doi: 10.1109/tac.1974.1100705.  Google Scholar [2] A. Beck, First-Order Methods in Optimization, MOS-SIAM Series on Optimization, 25. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2017. doi: 10.1137/1.9781611974997.ch1.  Google Scholar [3] A. Beck and M. Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Transactions on Image Processing, 18 (2009), 2419-2434.  doi: 10.1109/TIP.2009.2028250.  Google Scholar [4] D. Bertsimas, A. King and R. Mazumder, Best subset selection via a modern optimization lens, The Annals of Statistics, 44 (2016), 813-852.  doi: 10.1214/15-AOS1388.  Google Scholar [5] S. Billups, S. Dirkse and M. Ferris, A comparison of large scale mixed complementarity problem solvers, Computational Optimization and Applications, 7 (1997), 3-25.  doi: 10.1023/A:1008632215341.  Google Scholar [6] T. Blumensath, Accelerated iterative hard thresholding, Signal Processing, 92 (2012), 752-756.  doi: 10.1016/j.sigpro.2011.09.017.  Google Scholar [7] T. Blumensath and M. Davies, Iterative thresholding for sparse approximations, Journal of Fourier Analysis and Applications, 14 (2008), 629-654.  doi: 10.1007/s00041-008-9035-z.  Google Scholar [8] S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3 (2010), 1-122.  doi: 10.1561/9781601984616.  Google Scholar [9] K. Bredies and D. Lorenz, Regularization with non-convex separable constraints, Inverse Problems, 25 (2009), 085011. doi: 10.1088/0266-5611/25/8/085011.  Google Scholar [10] T. Cai and A. Zhang, Sharp RIP bound for sparse signal and low-rank matrix recovery, Applied and Computational Harmonic Analysis, 35 (2013), 74-93.  doi: 10.1016/j.acha.2012.07.010.  Google Scholar [11] E. Candes and T. Tao, Decoding by linear programming, IEEE Transactions on Information Theory, 51 (2005), 4203-4215.  doi: 10.1109/TIT.2005.858979.  Google Scholar [12] R. Chartrand, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Processing Letters, 14 (2007), 707-710.   Google Scholar [13] B. Chen and P. Harker, Smooth approximations to nonlinear complementarity problems, SIAM Journal on Optimization, 7 (1997), 403-420.  doi: 10.1137/S1052623495280615.  Google Scholar [14] C. Chen and O. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Computational Optimization and Applications, 5 (1996), 97-138.  doi: 10.1007/BF00249052.  Google Scholar [15] L. Chen and Y. Gu, The convergence guarantees of a non-convex approach for sparse recovery, IEEE Transactions on Signal Processing, 62 (2014), 3754-3767.  doi: 10.1109/TSP.2014.2330349.  Google Scholar [16] S. Chen, D. Donoho and M. Saunders, Atomic decomposition by basis pursuit, SIAM Review, 43 (2001), 129-159.  doi: 10.1137/S003614450037906X.  Google Scholar [17] X. Chen, Smoothing methods for nonsmooth, nonconvex minimization, Mathematical Programming, 134 (2012), 71-99.  doi: 10.1007/s10107-012-0569-0.  Google Scholar [18] X. Chen and L. Qi, A parameterized Newton method and a quasi-Newton method for nonsmooth equations, Computational Optimization and Applications, 3 (1994), 157-179.  doi: 10.1007/BF01300972.  Google Scholar [19] X. Chen, L. Qi and D. Sun, Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities, Mathematics of Computation of the American Mathematical Society, 67 (1998), 519-540.  doi: 10.1090/S0025-5718-98-00932-6.  Google Scholar [20] X. Chen and T. Yamamoto, Convergence domains of certain iterative methods for solving nonlinear equations, Numericacl Functional Analysis and Optimization, 10 (1989), 37-48.  doi: 10.1080/01630568908816289.  Google Scholar [21] I. Daubechies, M. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Communications on Pure and Applied Mathematics, 57 (2004), 1413-1457.  doi: 10.1002/cpa.20042.  Google Scholar [22] D. Donoho, Compressed sensing, IEEE Transactions on Information Theory, 52 (2006), 1289-1306.   Google Scholar [23] D. Donoho and X. Huo, Uncertainty principles and ideal atomic decomposition, IEEE Transactions on Information Theory, 47 (2001), 2845-2862.  doi: 10.1109/18.959265.  Google Scholar [24] J. Fan and R. Li, Variable selection via nonconcave penalized likelihood and its oracle properties, Journal of the American Statistical Association, 96 (2001), 1348-1360.  doi: 10.1198/016214501753382273.  Google Scholar [25] Q. Fan, Y. Jiao and X. Lu, A primal dual active set algorithm with continuation for compressed sensing, IEEE Transactions on Signal Processing, 62 (2014), 6276-6285.  doi: 10.1109/TSP.2014.2362880.  Google Scholar [26] M. Figueiredo, R. Nowak and S. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems, IEEE Journal of Selected Topics in Signal Processing, 1 (2007), 586-597.  doi: 10.1109/JSTSP.2007.910281.  Google Scholar [27] I. Frank and J. Friedman, A statistical view of some chemometrics regression tools, Technometrics, 35 (1993), 109-135.   Google Scholar [28] S. Gabriel and J. Moré, Smoothing of mixed complementarity problems, Complementarity and Variational Problems: State of the Art, (1997), 105–116.  Google Scholar [29] G. Gasso, A. Rakotomamonjy and S. Canu, Recovering sparse signals with a certain family of nonconvex penalties and DC programming, IEEE Transactions on Signal Processing, 57 (2009), 4686-4698.   Google Scholar [30] M. Grasmair, O. Scherzer and M. Haltmeier, Necessary and sufficient conditions for linear convergence of $\ell^1$-regularization, Communications on Pure and Applied Mathematics, 64 (2011), 161-182.  doi: 10.1002/cpa.20350.  Google Scholar [31] R. Griesse and D. Lorenz, A semismooth Newton method for Tikhonov functionals with sparsity constraints, Inverse Problems, 24 (2008), 035007. doi: 10.1088/0266-5611/24/3/035007.  Google Scholar [32] E. Hans and T. Raasch, Global convergence of damped semismooth Newton methods for $l_1$ Tikhonov regularization, Inverse Problems, 31 (2015), 025005. doi: 10.1088/0266-5611/31/2/025005.  Google Scholar [33] M. Hintermüller and T. Wu, A superlinearly convergent R-regularized Newton scheme for variational models with concave sparsity-promoting priors, Computational Optimization and Applications, 57 (2014), 1-25.  doi: 10.1007/s10589-013-9583-2.  Google Scholar [34] R. Horn and C. Johnson, Matrix Analysis, Cambridge university press, 2013.   Google Scholar [35] J. Huang, P. Breheny, S. Lee, S. Ma and C. Zhang, The Mnet method for variable selection, Statistica Sinica, 26 (2016), 903-923.   Google Scholar [36] J. Huang, Y. Jiao, B. Jin, J. Liu, X. Lu and C. Yang, A unified primal dual active set algorithm for nonconvex sparse recovery, Statistical Science, 36 (2021), 215-238.  doi: 10.1214/19-sts758.  Google Scholar [37] J. Huang, Y. Jiao, Y. Liu and X. Lu, A constructive approach to $L_0$ penalized regression, Journal of Machine Learning Research, 19 (2018), 403-439.   Google Scholar [38] Z. Huang, L. Qi and D. Sun, Sub-quadratic convergence of a smoothing Newton algorithm for the $P_0$-and monotone LCP, Mathematical Programming, 99 (2004), 423-441.  doi: 10.1007/s10107-003-0457-8.  Google Scholar [39] K. Ito and K. Kunisch, Optimal control with $L^p(\Omega), p\in [0, 1)$, control cost, SIAM Journal on Control and Optimization, 52 (2014), 1251-1275.  doi: 10.1137/120896529.  Google Scholar [40] Y. Jiao, B. Jin and X. Lu, A primal dual active set with continuation algorithm for the $\ell_0$-regularized optimization problem, Applied and Computational Harmonic Analysis, 39 (2015), 400-426.  doi: 10.1016/j.acha.2014.10.001.  Google Scholar [41] Y. Jiao, Q. Jin, X. Lu and W. Wang, Alternating direction method of multipliers for linear inverse problems, SIAM Journal on Numerical Analysis, 54 (2016), 2114-2137.  doi: 10.1137/15M1029308.  Google Scholar [42] Y. Jiao, Q. Jin, X. Lu and W. Wang, Preconditioned alternating direction method of multipliers for inverse problems with constraints, Inverse Problems, 33 (2017), 025004. doi: 10.1088/1361-6420/33/2/025004.  Google Scholar [43] B. Jin, D. Lorenz and S. Schiffler, Elastic-net regularization: Error estimates and active set methods, Inverse Problems, 25 (2009), 115022. doi: 10.1088/0266-5611/25/11/115022.  Google Scholar [44] B. Kummer, Newton's method for non-differentiable functions, Advances in mathematical optimization, 45 (1988), 114-125.   Google Scholar [45] X. Li, D. Sun and K. Toh, A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems, SIAM Journal on Optimization, 28 (2018), 433-458.  doi: 10.1137/16M1097572.  Google Scholar [46] R. Mazumder, J. Friedman and T. Hastie, SparseNet: Coordinate descent with nonconvex penalties, Journal of the American Statistical Association, 106 (2011), 1125-1138.  doi: 10.1198/jasa.2011.tm09738.  Google Scholar [47] M. Osborne, B. Presnell and B. Turlach, A new approach to variable selection in least squares problems, IMA Journal of Numerical Analysis, 20 (2000), 389-403.  doi: 10.1093/imanum/20.3.389.  Google Scholar [48] L. Qi and X. Chen, A globally convergent successive approximation method for severely nonsmooth equations, SIAM Journal on Control and Optimization, 33 (1995), 402-418.  doi: 10.1137/S036301299223619X.  Google Scholar [49] L. Qi and D. Sun, Smoothing functions and smoothing Newton method for complementarity and variational inequality problems, Journal of Optimization Theory and Applications, 113 (2002), 121-147.  doi: 10.1023/A:1014861331301.  Google Scholar [50] R. Ramlau and G. Teschke, A Tikhonov-based projection iteration for nonlinear ill-posed problems with sparsity constraints, Numerische Mathematik, 104 (2006), 177-203.  doi: 10.1007/s00211-006-0016-3.  Google Scholar [51] R. Tibshirani, Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society: Series B (Methodological), 58 (1996), 267-288.  doi: 10.1111/j.2517-6161.1996.tb02080.x.  Google Scholar [52] P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of Optimization Theory and Applications, 109 (2001), 475-494.  doi: 10.1023/A:1017501703105.  Google Scholar [53] L. Wang, Q. Zhao, J. Gao, Z. Xu, M. Fehler and X. Jiang, Seismic sparse-spike deconvolution via Toeplitz-sparse matrix factorization, Geophysics, 81 (2016), 169-182.  doi: 10.1190/geo2015-0151.1.  Google Scholar [54] W. Wang, S. Lu, H. Mao and J. Cheng, Multi-parameter Tikhonov regularization with the $\ell^0$ sparsity constraint, Inverse Problems, 29 (2013), 065018. doi: 10.1088/0266-5611/29/6/065018.  Google Scholar [55] C. Yi and J. Huang, Semismooth newton coordinate descent algorithm for elastic-net penalized huber loss regression and quantile regression, Journal of Computational and Graphical Statistics, 26 (2017), 547-557.  doi: 10.1080/10618600.2016.1256816.  Google Scholar [56] C. Zhang, Nearly unbiased variable selection under minimax concave penalty, The Annals of Statistics, 38 (2010), 894-942.  doi: 10.1214/09-AOS729.  Google Scholar [57] C. H. Zhang and T. Zhang, A general theory of concave regularization for high-dimensional sparse estimation problems, Statistical Science, 27 (2012), 576-593.  doi: 10.1214/12-STS399.  Google Scholar [58] T. Zhang, Adaptive forward-backward greedy algorithm for learning sparse representations, IEEE Transactions on Information Theory, 57 (2011), 4689-4708.  doi: 10.1109/TIT.2011.2146690.  Google Scholar [59] H. Zou and T. Hastie, Regularization and variable selection via the elastic net, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67 (2005), 301-320.  doi: 10.1111/j.1467-9868.2005.00503.x.  Google Scholar

show all references

##### References:
 [1] H. Akaike, A new look at the statistical model identification, IEEE Transactions on Automatic Control, 19 (1974), 716-723.  doi: 10.1109/tac.1974.1100705.  Google Scholar [2] A. Beck, First-Order Methods in Optimization, MOS-SIAM Series on Optimization, 25. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2017. doi: 10.1137/1.9781611974997.ch1.  Google Scholar [3] A. Beck and M. Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Transactions on Image Processing, 18 (2009), 2419-2434.  doi: 10.1109/TIP.2009.2028250.  Google Scholar [4] D. Bertsimas, A. King and R. Mazumder, Best subset selection via a modern optimization lens, The Annals of Statistics, 44 (2016), 813-852.  doi: 10.1214/15-AOS1388.  Google Scholar [5] S. Billups, S. Dirkse and M. Ferris, A comparison of large scale mixed complementarity problem solvers, Computational Optimization and Applications, 7 (1997), 3-25.  doi: 10.1023/A:1008632215341.  Google Scholar [6] T. Blumensath, Accelerated iterative hard thresholding, Signal Processing, 92 (2012), 752-756.  doi: 10.1016/j.sigpro.2011.09.017.  Google Scholar [7] T. Blumensath and M. Davies, Iterative thresholding for sparse approximations, Journal of Fourier Analysis and Applications, 14 (2008), 629-654.  doi: 10.1007/s00041-008-9035-z.  Google Scholar [8] S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3 (2010), 1-122.  doi: 10.1561/9781601984616.  Google Scholar [9] K. Bredies and D. Lorenz, Regularization with non-convex separable constraints, Inverse Problems, 25 (2009), 085011. doi: 10.1088/0266-5611/25/8/085011.  Google Scholar [10] T. Cai and A. Zhang, Sharp RIP bound for sparse signal and low-rank matrix recovery, Applied and Computational Harmonic Analysis, 35 (2013), 74-93.  doi: 10.1016/j.acha.2012.07.010.  Google Scholar [11] E. Candes and T. Tao, Decoding by linear programming, IEEE Transactions on Information Theory, 51 (2005), 4203-4215.  doi: 10.1109/TIT.2005.858979.  Google Scholar [12] R. Chartrand, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Processing Letters, 14 (2007), 707-710.   Google Scholar [13] B. Chen and P. Harker, Smooth approximations to nonlinear complementarity problems, SIAM Journal on Optimization, 7 (1997), 403-420.  doi: 10.1137/S1052623495280615.  Google Scholar [14] C. Chen and O. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Computational Optimization and Applications, 5 (1996), 97-138.  doi: 10.1007/BF00249052.  Google Scholar [15] L. Chen and Y. Gu, The convergence guarantees of a non-convex approach for sparse recovery, IEEE Transactions on Signal Processing, 62 (2014), 3754-3767.  doi: 10.1109/TSP.2014.2330349.  Google Scholar [16] S. Chen, D. Donoho and M. Saunders, Atomic decomposition by basis pursuit, SIAM Review, 43 (2001), 129-159.  doi: 10.1137/S003614450037906X.  Google Scholar [17] X. Chen, Smoothing methods for nonsmooth, nonconvex minimization, Mathematical Programming, 134 (2012), 71-99.  doi: 10.1007/s10107-012-0569-0.  Google Scholar [18] X. Chen and L. Qi, A parameterized Newton method and a quasi-Newton method for nonsmooth equations, Computational Optimization and Applications, 3 (1994), 157-179.  doi: 10.1007/BF01300972.  Google Scholar [19] X. Chen, L. Qi and D. Sun, Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities, Mathematics of Computation of the American Mathematical Society, 67 (1998), 519-540.  doi: 10.1090/S0025-5718-98-00932-6.  Google Scholar [20] X. Chen and T. Yamamoto, Convergence domains of certain iterative methods for solving nonlinear equations, Numericacl Functional Analysis and Optimization, 10 (1989), 37-48.  doi: 10.1080/01630568908816289.  Google Scholar [21] I. Daubechies, M. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Communications on Pure and Applied Mathematics, 57 (2004), 1413-1457.  doi: 10.1002/cpa.20042.  Google Scholar [22] D. Donoho, Compressed sensing, IEEE Transactions on Information Theory, 52 (2006), 1289-1306.   Google Scholar [23] D. Donoho and X. Huo, Uncertainty principles and ideal atomic decomposition, IEEE Transactions on Information Theory, 47 (2001), 2845-2862.  doi: 10.1109/18.959265.  Google Scholar [24] J. Fan and R. Li, Variable selection via nonconcave penalized likelihood and its oracle properties, Journal of the American Statistical Association, 96 (2001), 1348-1360.  doi: 10.1198/016214501753382273.  Google Scholar [25] Q. Fan, Y. Jiao and X. Lu, A primal dual active set algorithm with continuation for compressed sensing, IEEE Transactions on Signal Processing, 62 (2014), 6276-6285.  doi: 10.1109/TSP.2014.2362880.  Google Scholar [26] M. Figueiredo, R. Nowak and S. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems, IEEE Journal of Selected Topics in Signal Processing, 1 (2007), 586-597.  doi: 10.1109/JSTSP.2007.910281.  Google Scholar [27] I. Frank and J. Friedman, A statistical view of some chemometrics regression tools, Technometrics, 35 (1993), 109-135.   Google Scholar [28] S. Gabriel and J. Moré, Smoothing of mixed complementarity problems, Complementarity and Variational Problems: State of the Art, (1997), 105–116.  Google Scholar [29] G. Gasso, A. Rakotomamonjy and S. Canu, Recovering sparse signals with a certain family of nonconvex penalties and DC programming, IEEE Transactions on Signal Processing, 57 (2009), 4686-4698.   Google Scholar [30] M. Grasmair, O. Scherzer and M. Haltmeier, Necessary and sufficient conditions for linear convergence of $\ell^1$-regularization, Communications on Pure and Applied Mathematics, 64 (2011), 161-182.  doi: 10.1002/cpa.20350.  Google Scholar [31] R. Griesse and D. Lorenz, A semismooth Newton method for Tikhonov functionals with sparsity constraints, Inverse Problems, 24 (2008), 035007. doi: 10.1088/0266-5611/24/3/035007.  Google Scholar [32] E. Hans and T. Raasch, Global convergence of damped semismooth Newton methods for $l_1$ Tikhonov regularization, Inverse Problems, 31 (2015), 025005. doi: 10.1088/0266-5611/31/2/025005.  Google Scholar [33] M. Hintermüller and T. Wu, A superlinearly convergent R-regularized Newton scheme for variational models with concave sparsity-promoting priors, Computational Optimization and Applications, 57 (2014), 1-25.  doi: 10.1007/s10589-013-9583-2.  Google Scholar [34] R. Horn and C. Johnson, Matrix Analysis, Cambridge university press, 2013.   Google Scholar [35] J. Huang, P. Breheny, S. Lee, S. Ma and C. Zhang, The Mnet method for variable selection, Statistica Sinica, 26 (2016), 903-923.   Google Scholar [36] J. Huang, Y. Jiao, B. Jin, J. Liu, X. Lu and C. Yang, A unified primal dual active set algorithm for nonconvex sparse recovery, Statistical Science, 36 (2021), 215-238.  doi: 10.1214/19-sts758.  Google Scholar [37] J. Huang, Y. Jiao, Y. Liu and X. Lu, A constructive approach to $L_0$ penalized regression, Journal of Machine Learning Research, 19 (2018), 403-439.   Google Scholar [38] Z. Huang, L. Qi and D. Sun, Sub-quadratic convergence of a smoothing Newton algorithm for the $P_0$-and monotone LCP, Mathematical Programming, 99 (2004), 423-441.  doi: 10.1007/s10107-003-0457-8.  Google Scholar [39] K. Ito and K. Kunisch, Optimal control with $L^p(\Omega), p\in [0, 1)$, control cost, SIAM Journal on Control and Optimization, 52 (2014), 1251-1275.  doi: 10.1137/120896529.  Google Scholar [40] Y. Jiao, B. Jin and X. Lu, A primal dual active set with continuation algorithm for the $\ell_0$-regularized optimization problem, Applied and Computational Harmonic Analysis, 39 (2015), 400-426.  doi: 10.1016/j.acha.2014.10.001.  Google Scholar [41] Y. Jiao, Q. Jin, X. Lu and W. Wang, Alternating direction method of multipliers for linear inverse problems, SIAM Journal on Numerical Analysis, 54 (2016), 2114-2137.  doi: 10.1137/15M1029308.  Google Scholar [42] Y. Jiao, Q. Jin, X. Lu and W. Wang, Preconditioned alternating direction method of multipliers for inverse problems with constraints, Inverse Problems, 33 (2017), 025004. doi: 10.1088/1361-6420/33/2/025004.  Google Scholar [43] B. Jin, D. Lorenz and S. Schiffler, Elastic-net regularization: Error estimates and active set methods, Inverse Problems, 25 (2009), 115022. doi: 10.1088/0266-5611/25/11/115022.  Google Scholar [44] B. Kummer, Newton's method for non-differentiable functions, Advances in mathematical optimization, 45 (1988), 114-125.   Google Scholar [45] X. Li, D. Sun and K. Toh, A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems, SIAM Journal on Optimization, 28 (2018), 433-458.  doi: 10.1137/16M1097572.  Google Scholar [46] R. Mazumder, J. Friedman and T. Hastie, SparseNet: Coordinate descent with nonconvex penalties, Journal of the American Statistical Association, 106 (2011), 1125-1138.  doi: 10.1198/jasa.2011.tm09738.  Google Scholar [47] M. Osborne, B. Presnell and B. Turlach, A new approach to variable selection in least squares problems, IMA Journal of Numerical Analysis, 20 (2000), 389-403.  doi: 10.1093/imanum/20.3.389.  Google Scholar [48] L. Qi and X. Chen, A globally convergent successive approximation method for severely nonsmooth equations, SIAM Journal on Control and Optimization, 33 (1995), 402-418.  doi: 10.1137/S036301299223619X.  Google Scholar [49] L. Qi and D. Sun, Smoothing functions and smoothing Newton method for complementarity and variational inequality problems, Journal of Optimization Theory and Applications, 113 (2002), 121-147.  doi: 10.1023/A:1014861331301.  Google Scholar [50] R. Ramlau and G. Teschke, A Tikhonov-based projection iteration for nonlinear ill-posed problems with sparsity constraints, Numerische Mathematik, 104 (2006), 177-203.  doi: 10.1007/s00211-006-0016-3.  Google Scholar [51] R. Tibshirani, Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society: Series B (Methodological), 58 (1996), 267-288.  doi: 10.1111/j.2517-6161.1996.tb02080.x.  Google Scholar [52] P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of Optimization Theory and Applications, 109 (2001), 475-494.  doi: 10.1023/A:1017501703105.  Google Scholar [53] L. Wang, Q. Zhao, J. Gao, Z. Xu, M. Fehler and X. Jiang, Seismic sparse-spike deconvolution via Toeplitz-sparse matrix factorization, Geophysics, 81 (2016), 169-182.  doi: 10.1190/geo2015-0151.1.  Google Scholar [54] W. Wang, S. Lu, H. Mao and J. Cheng, Multi-parameter Tikhonov regularization with the $\ell^0$ sparsity constraint, Inverse Problems, 29 (2013), 065018. doi: 10.1088/0266-5611/29/6/065018.  Google Scholar [55] C. Yi and J. Huang, Semismooth newton coordinate descent algorithm for elastic-net penalized huber loss regression and quantile regression, Journal of Computational and Graphical Statistics, 26 (2017), 547-557.  doi: 10.1080/10618600.2016.1256816.  Google Scholar [56] C. Zhang, Nearly unbiased variable selection under minimax concave penalty, The Annals of Statistics, 38 (2010), 894-942.  doi: 10.1214/09-AOS729.  Google Scholar [57] C. H. Zhang and T. Zhang, A general theory of concave regularization for high-dimensional sparse estimation problems, Statistical Science, 27 (2012), 576-593.  doi: 10.1214/12-STS399.  Google Scholar [58] T. Zhang, Adaptive forward-backward greedy algorithm for learning sparse representations, IEEE Transactions on Information Theory, 57 (2011), 4689-4708.  doi: 10.1109/TIT.2011.2146690.  Google Scholar [59] H. Zou and T. Hastie, Regularization and variable selection via the elastic net, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67 (2005), 301-320.  doi: 10.1111/j.1467-9868.2005.00503.x.  Google Scholar
From left to right: the hard thresholding operator $T_{2}(x)$ and corresponding approximations with uniform smoothing function for different $\epsilon$
The density function
The limiting form
Results of random Gaussian matrix with a correlation coefficient $\tilde{\nu} = 0.2$ for strict sparse signal with $n = 1000, p = 2000, \delta = 1e-1, \lambda = 6.3e-01$
Results of random Gaussian matrix with a correlation coefficient $\tilde{\nu} = 0.2$ for non-strict sparse signal with $n = 1000, p = 2000, \delta = 1e-1, \lambda = 2.1e-01$
Results of Heaviside matrix for strict sparse signal with $n = 1000, p = 1000, \delta = 1e-1, \lambda = 2.3e-01$
Results of Heaviside matrix for non-strict sparse signal with $n = 1000, p = 1000, \delta = 1e-1, \lambda = 1.2e-02$
Results of inverse Laplace matrix for strict sparse signal with $n = 1000, p = 1000, \delta = 1e-3, \lambda = 1.4e-09$
Results of inverse Laplace matrix for non-strict sparse signal with $n = 1000, p = 1000, \delta = 1e-4, \lambda = 7.1e-11$
Results of Toeplitz matrix with $n = 1000, p = 1000, \delta = 1e-1, \lambda = 4.5e-01$
Results of partial Toeplitz matrix with $n = 500, p = 1000, \delta = 1e-1, \lambda = 4.6e-01$
The exact recovery probability of the support of SNM, LASSO, MCP and SCAD
The exact recovery probability of the support of SNM, AIHT and FoBa for the same model (5)
The results of relative error $RelErr$ of all the solvers considered here
 Methods Gaussian matrix ($0.3$) Gaussian matrix ($0.8$) Heaviside matrix SNM 2.7e-07 (7.1e-08) 3.2e-07 (1.1e-07) 1.8e-06 (8.5e-07) AIHT 1.4e-03 (9.8e-03) 1.1e-01 (1.2e-01) 1.3e-01 (9.0e-02) FoBa 2.1e-07 (4.4e-08) 1.3e-01 (1.8e-01) 9.0e-07 (3.1e-07) LASSO 3.1e-02 (1.3e-03) 4.9e-02 (3.4e-02) 1.7e-01 (7.1e-02) MCP 2.1e-07 (4.4e-08) 1.1e-01 (1.3e-01) 1.4e-01 (3.5e-01) SCAD 2.1e-07 (4.4e-08) 8.9e-03 (5.2e-02) 9.0e-07 (3.1e-07)
 Methods Gaussian matrix ($0.3$) Gaussian matrix ($0.8$) Heaviside matrix SNM 2.7e-07 (7.1e-08) 3.2e-07 (1.1e-07) 1.8e-06 (8.5e-07) AIHT 1.4e-03 (9.8e-03) 1.1e-01 (1.2e-01) 1.3e-01 (9.0e-02) FoBa 2.1e-07 (4.4e-08) 1.3e-01 (1.8e-01) 9.0e-07 (3.1e-07) LASSO 3.1e-02 (1.3e-03) 4.9e-02 (3.4e-02) 1.7e-01 (7.1e-02) MCP 2.1e-07 (4.4e-08) 1.1e-01 (1.3e-01) 1.4e-01 (3.5e-01) SCAD 2.1e-07 (4.4e-08) 8.9e-03 (5.2e-02) 9.0e-07 (3.1e-07)
 [1] Lianjun Zhang, Lingchen Kong, Yan Li, Shenglong Zhou. A smoothing iterative method for quantile regression with nonconvex $\ell_p$ penalty. Journal of Industrial & Management Optimization, 2017, 13 (1) : 93-112. doi: 10.3934/jimo.2016006 [2] Chengxiang Wang, Li Zeng, Wei Yu, Liwei Xu. Existence and convergence analysis of $\ell_{0}$ and $\ell_{2}$ regularizations for limited-angle CT reconstruction. Inverse Problems & Imaging, 2018, 12 (3) : 545-572. doi: 10.3934/ipi.2018024 [3] Qia Li, Na Zhang. Capped $\ell_p$ approximations for the composite $\ell_0$ regularization problem. Inverse Problems & Imaging, 2018, 12 (5) : 1219-1243. doi: 10.3934/ipi.2018051 [4] Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial & Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53 [5] Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial & Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057 [6] Jun Wang, Xing Tao Wang. Sparse signal reconstruction via the approximations of $\ell_{0}$ quasinorm. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1907-1925. doi: 10.3934/jimo.2019035 [7] Pengbo Geng, Wengu Chen. Unconstrained $\ell_1$-$\ell_2$ minimization for sparse recovery via mutual coherence. Mathematical Foundations of Computing, 2020, 3 (2) : 65-79. doi: 10.3934/mfc.2020006 [8] Qing Ma, Yanjun Wang. Distributionally robust chance constrained svm model with $\ell_2$-Wasserstein distance. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021212 [9] Zheng-Hai Huang, Nan Lu. Global and global linear convergence of smoothing algorithm for the Cartesian $P_*(\kappa)$-SCLCP. Journal of Industrial & Management Optimization, 2012, 8 (1) : 67-86. doi: 10.3934/jimo.2012.8.67 [10] Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial & Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485 [11] Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115 [12] Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial & Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381 [13] Hengrui Luo, Alice Patania, Jisu Kim, Mikael Vejdemo-Johansson. Generalized penalty for circular coordinate representation. Foundations of Data Science, 2021, 3 (4) : 729-767. doi: 10.3934/fods.2021024 [14] Jianguo Huang, Sen Lin. A $C^0P_2$ time-stepping virtual element method for linear wave equations on polygonal meshes. Electronic Research Archive, 2020, 28 (2) : 911-933. doi: 10.3934/era.2020048 [15] Na Zhao, Zheng-Hai Huang. A nonmonotone smoothing Newton algorithm for solving box constrained variational inequalities with a $P_0$ function. Journal of Industrial & Management Optimization, 2011, 7 (2) : 467-482. doi: 10.3934/jimo.2011.7.467 [16] Xiaojiao Tong, Shuzi Zhou. A smoothing projected Newton-type method for semismooth equations with bound constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235 [17] Victor Churchill, Rick Archibald, Anne Gelb. Edge-adaptive $\ell_2$ regularization image reconstruction from non-uniform Fourier data. Inverse Problems & Imaging, 2019, 13 (5) : 931-958. doi: 10.3934/ipi.2019042 [18] Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102 [19] Yibing Lv, Zhongping Wan. Linear bilevel multiobjective optimization problem: Penalty approach. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1213-1223. doi: 10.3934/jimo.2018092 [20] Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965

2020 Impact Factor: 1.639

## Tools

Article outline

Figures and Tables