×

A truncated Newton algorithm for nonconvex sparse recovery. (English) Zbl 1493.90180

Summary: Some second-order sufficient conditions are established for problems with \(\ell_1\), SCAD and MCP penalties respectively and then an algorithm with active set strategy is proposed for solving \(\ell_1\), SCAD and MCP penalties based on an approximation of the second order sufficient conditions. The active sets are estimated by an identification technique to identify accurately zero components in a neighborhood of a critical point of \(\ell_1\), SCAD and MCP penalties. In the algorithm, a truncated Newton direction is used to update the free variables, while \(d^k = - x^k\) is used to update the active variables. To accelerate the convergence, a nonmonotone line search strategy is used to guarantee global convergence. Numerical results illustrate that the proposed algorithm is competitive with several well-known methods.

MSC:

90C30 Nonlinear programming

Software:

FPC_AS; Sparco
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahn, M.; Pang, J. S.; Xin, J., Difference-of-convex learning: directional stationarity, optimality, and sparsity, SIAM J. Optim., 27, 3, 1637-1655 (2017) · Zbl 1369.90130
[2] Afonso, M.; Bioucas-Dias, J.; Figueiredo, M., Fast image recovery using variable splitting and constrained optimization, IEEE Trans. Image Process., 19, 9, 2345-2356 (2010) · Zbl 1371.94018
[3] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202 (2009) · Zbl 1175.94009
[4] Bian, W.; Chen, X.; Ye, Y. Y., Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization, Math. Program., 149, 1-2, 301-327 (2015) · Zbl 1318.90075
[5] Bian, W.; Chen, X., A smoothing proximal gradient algorithm for nonsmooth convex regression with cardinality penalty, SIAM J. Numer. Anal., 58, 1, 858-883 (2020)
[6] Van den Berg, E.; Friedlander, M. P.; Hennenfent, G.; Herrmann, F. J.; Saab, R.; Yilmaz, Ö., Algorithm 890: Sparco: a testing framework for sparse reconstruction, ACM Trans. Math. Softw., 35, 4, 1-16 (2009)
[7] Bruckstein, A. M.; Donoho, D. L.; Elad, M., From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51, 1, 34-81 (2009) · Zbl 1178.68619
[8] Candes, E. J.; Wakin, M. B.; Boyd, S. P., Enhancing sparsity by reweighted \(\ell_1\) minimization, J. Fourier Anal. Appl., 14, 877-905 (2008) · Zbl 1176.94014
[9] Chen, X.; Xu, F.; Ye, Y. Y., Lower bound theory of nonzero entries in solutions of \(\ell_2- \ell_p\) minimization, SIAM J. Imaging Sci., 32, 5, 2832-2852 (2010) · Zbl 1242.90174
[10] Chen, X.; Niu, L. F.; Yuan, Y. X., Optimality conditions and a smoothing trust region Newton method for nonlipschitz optimization, SIAM J. Optim., 23, 3, 1528-1552 (2013) · Zbl 1291.90238
[11] Cheng, W. Y.; Dai, Y. H., Gradient-based method with active set strategy for \(\ell_1\) optimization, Math. Comput., 87, 311, 1283-1305 (2018) · Zbl 1392.90079
[12] Cheng, W. Y.; Zhou, H. L.; Guo, Z. T., A second order algorithm for MCP regularized optimization, IEEE Access (2022)
[13] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213 (2002) · Zbl 1049.90004
[14] Fan, J.; Li, R., Variable selection via nonconcave penalized likelihood and its oracle properties, J. Am. Stat. Assoc., 96, 456, 1348-1360 (2001) · Zbl 1073.62547
[15] Figueiredo, M. A.T.; Nowak, R. D.; Wright, S. J., Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Signal Process., 1, 4, 586-597 (2007)
[16] Gong, P.; Zhang, C.; Lu, Z.; Huang, J.; Ye, J., A general iterative shrinkage and thresholding algorithm for non-convex regularized optimization problems, (Proc. 30th Int. Conf. Mach. Learn.. Proc. 30th Int. Conf. Mach. Learn., ICML-13 (2013)), 37-45
[17] Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone line search technique for Newton’s method, SIAM J. Numer. Anal., 23, 4, 707-716 (1986) · Zbl 0616.65067
[18] Grippo, L.; Lampariello, F.; Lucidi, S., A truncated Newton method with nonmonotone line search for unconstrained optimization, J. Optim. Theory Appl., 60, 3, 401-419 (1989) · Zbl 0632.90059
[19] Hager, W. W.; Phan, D. T.; Zhang, H., Gradient-based methods for sparse recovery, SIAM J. Imaging Sci., 4, 1, 146-165 (2011) · Zbl 1209.90266
[20] Jiang, B.; Lin, T. Y.; Ma, S. Q.; Zhang, S. Z., Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis, Comput. Appl. Math., 72, 115-157 (2019) · Zbl 1411.90274
[21] Jiao, Y. L.; Jin, B. T.; Lu, X. L.; Ren, W., A unified primal dual active set algorithm for nonconvex sparse recovery, Stat. Sci., 36, 2, 215-238 (2021) · Zbl 07368234
[22] Le Thi, H. A.; Le, H. M.; Dinh, T. P., Feature selection in machine learning: an exact penalty approach using a difference of convex function algorithm, Mach. Learn., 101, 1-3, 163-186 (2014) · Zbl 1343.68201
[23] Kim, S. J.; Koh, K.; Lustig, M.; Boyd, S.; Gorinevsky, D., An interior-point method for large-scale \(\ell_1\)-regularized least squares, IEEE J. Sel. Top. Signal Process., 1, 4, 606-617 (2007)
[24] Soubies, E.; Blanc-Féraud, L.; Aubert, G., A unified view of exact continuous penalties for \(\ell_2- \ell_0\) minimization, SIAM J. Optim., 27, 3, 2034-2060 (2017) · Zbl 1375.65086
[25] Tseng, P.; Yun, S. W., A coordinate gradient descent method for nonsmooth separable minimization, Math. Program., 117, 387-423 (2019) · Zbl 1166.90016
[26] Wen, Z. W.; Yin, W. T.; Goldfarb, D.; Zhang, Y., A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation, SIAM J. Sci. Comput., 32, 4, 1832-1857 (2010) · Zbl 1215.49039
[27] Wright, J.; Nowak, R. D.; Figueiredo, M. A.T., Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57, 7, 2479-2493 (2009) · Zbl 1391.94442
[28] Zhang, T., Multi-stage convex relaxation for learning with sparse regularization, Adv. Neural Inf. Process. Syst., 22, 1929-1936 (2009)
[29] Zhang, C. H., Nearly unbiased variable selection under minimax concave penalty, Ann. Stat., 38, 2, 894-942 (2010) · Zbl 1183.62120
[30] Zou, H., The adaptive lasso and its oracle properties, J. Am. Stat. Assoc., 101, 476, 1418-1429 (2006) · Zbl 1171.62326
[31] Zhang, S.; Xin, J., Minimization of transformed \(\ell_1\) penalty: theory difference of convex function algorithm, and robust application in compressing sensing, Math. Program., Ser. B, 169, 307-336 (2018) · Zbl 1386.94049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.