Gradient-based method with active set strategy for $\ell _1$ optimization
HTML articles powered by AMS MathViewer
- by Wanyou Cheng and Yu-Hong Dai PDF
- Math. Comp. 87 (2018), 1283-1305 Request permission
Abstract:
In this paper, we propose an identification function and develop an active set identification technique for solving the $\ell _1$ optimization problem. Such a technique has a strong ability to accurately identify the zero components in a neighbourhood of an isolated stationary point without strict complementarity conditions. Based on the active set identification technique, we propose a gradient-based method for the $\ell _1$ optimization problem. To accelerate the algorithm, a subspace Barzilai-Borwein steplength and a subspace exact steplength are developed, respectively. Under appropriate conditions, we show that the method with the nonmonotone line search technique is globally convergent. Numerical experiments with compressive sensing problems show that our approach is competitive with several known methods for the standard $\ell _2$-$\ell _1$ problem.References
- Manya V. Afonso, José M. Bioucas-Dias, and Mário A. T. Figueiredo, Fast image recovery using variable splitting and constrained optimization, IEEE Trans. Image Process. 19 (2010), no. 9, 2345–2356. MR 2798930, DOI 10.1109/TIP.2010.2047910
- N. S. Aybat and G. Iyengar, A first-order smoothed penalty method for compressed sensing, SIAM J. Optim. 21 (2011), no. 1, 287–313. MR 2783217, DOI 10.1137/090762294
- N. S. Aybat and G. Iyengar, A first-order augmented Lagrangian method for compressed sensing, SIAM J. Optim. 22 (2012), no. 2, 429–459. MR 2968861, DOI 10.1137/100786721
- Jonathan Barzilai and Jonathan M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal. 8 (1988), no. 1, 141–148. MR 967848, DOI 10.1093/imanum/8.1.141
- Amir Beck and Marc Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009), no. 1, 183–202. MR 2486527, DOI 10.1137/080716542
- Amir Beck and Yonina C. Eldar, Sparsity constrained nonlinear optimization: optimality conditions and algorithms, SIAM J. Optim. 23 (2013), no. 3, 1480–1509. MR 3080197, DOI 10.1137/120869778
- José M. Bioucas-Dias and Mário A. T. Figueiredo, A new TwIST: two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Trans. Image Process. 16 (2007), no. 12, 2992–3004. MR 2472806, DOI 10.1109/TIP.2007.909319
- Ernesto G. Birgin, José Mario Martínez, and Marcos Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim. 10 (2000), no. 4, 1196–1211. MR 1777088, DOI 10.1137/S1052623497330963
- Daniel Boley, Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs, SIAM J. Optim. 23 (2013), no. 4, 2183–2207. MR 3123832, DOI 10.1137/120878951
- Alfred M. Bruckstein, David L. Donoho, and Michael Elad, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev. 51 (2009), no. 1, 34–81. MR 2481111, DOI 10.1137/060657704
- James V. Burke and Jorge J. Moré, On the identification of active constraints, SIAM J. Numer. Anal. 25 (1988), no. 5, 1197–1211. MR 960873, DOI 10.1137/0725068
- E. Candes and J. Romberg, $\ell _1$-magic: A collection of MATLAB Routines for Solving the Convex Optimization Programs Central to Compressive Sampling 2006 [Online]. Available: www.acm.caltech. edu/l1magic/
- Wanyou Cheng and Zixin Chen, Nonmonotone spectral method for large-scale symmetric nonlinear equations, Numer. Algorithms 62 (2013), no. 1, 149–162. MR 3009560, DOI 10.1007/s11075-012-9572-z
- Y. H. Dai, A new analysis on the Barzilai-Borwein gradient method, J. Oper. Res. Soc. China. 1 (2013), pp. 187–198.
- Yu-Hong Dai and Roger Fletcher, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming, Numer. Math. 100 (2005), no. 1, 21–47. MR 2129700, DOI 10.1007/s00211-004-0569-y
- Yu-Hong Dai, William W. Hager, Klaus Schittkowski, and Hongchao Zhang, The cyclic Barzilai-Borwein method for unconstrained optimization, IMA J. Numer. Anal. 26 (2006), no. 3, 604–627. MR 2241317, DOI 10.1093/imanum/drl006
- Yu-Hong Dai and Li-Zhi Liao, R-linear convergence of the Barzilai and Borwein gradient method, IMA J. Numer. Anal. 22 (2002), no. 1, 1–10. MR 1880051, DOI 10.1093/imanum/22.1.1
- Ingrid Daubechies, Michel Defrise, and Christine De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math. 57 (2004), no. 11, 1413–1457. MR 2077704, DOI 10.1002/cpa.20042
- G. Davis, S. Mallat, and M. Avellaneda, Adaptive greedy approximations, Constr. Approx. 13 (1997), no. 1, 57–98. MR 1424364, DOI 10.1007/s003659900033
- David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289–1306. MR 2241189, DOI 10.1109/TIT.2006.871582
- David L. Donoho, Michael Elad, and Vladimir N. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Inform. Theory 52 (2006), no. 1, 6–18. MR 2237332, DOI 10.1109/TIT.2005.860430
- Elizabeth D. Dolan and Jorge J. Moré, Benchmarking optimization software with performance profiles, Math. Program. 91 (2002), no. 2, Ser. A, 201–213. MR 1875515, DOI 10.1007/s101070100263
- Michael Elad, Boaz Matalon, and Michael Zibulevsky, Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization, Appl. Comput. Harmon. Anal. 23 (2007), no. 3, 346–367. MR 2362407, DOI 10.1016/j.acha.2007.02.002
- Mário A. T. Figueiredo and Robert D. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process. 12 (2003), no. 8, 906–916. MR 2008658, DOI 10.1109/TIP.2003.814255
- M. A. T. Figueiredo, R. D. Nowak, and S. J. Wright, Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Signal Process. 1 (2007), pp. 586–597.
- Kimon Fountoulakis and Jacek Gondzio, A second-order method for strongly convex $\ell _1$-regularization problems, Math. Program. 156 (2016), no. 1-2, Ser. A, 189–219. MR 3459199, DOI 10.1007/s10107-015-0875-4
- L. Grippo, F. Lampariello, and S. Lucidi, A nonmonotone line search technique for Newton’s method, SIAM J. Numer. Anal. 23 (1986), no. 4, 707–716. MR 849278, DOI 10.1137/0723046
- Elaine T. Hale, Wotao Yin, and Yin Zhang, Fixed-point continuation for $l_1$-minimization: methodology and convergence, SIAM J. Optim. 19 (2008), no. 3, 1107–1130. MR 2460734, DOI 10.1137/070698920
- William W. Hager, Dzung T. Phan, and Hongchao Zhang, Gradient-based methods for sparse recovery, SIAM J. Imaging Sci. 4 (2011), no. 1, 146–165. MR 2792408, DOI 10.1137/090775063
- S. J. Kim, K. Koh, M. Lustig, S. Boyd, and D. Gorinevsky, An interior-point method for large-scale $\ell _1$-regularized least squares, IEEE J. Sel. Top. Signal Process. 1 (2007), pp. 606–617.
- N. S. Keskar, J. Nocedal, F. Öztoprak, and A. Wächter, A second-order method for convex $\ell _1$-regularized optimization with active set prediction, http://arxiv.org/abs/1505.04315
- Y. Nesterov, Gradient methods for minimizing composite objective function, 2007, CORE Discussion Paper 2007/76 [Online]. Available: http://www.optimization-online.org/DB_HTML/2007/09/1784.html
- R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683
- Stephen M. Robinson, Linear convergence of epsilon-subgradient descent methods for a class of convex functions, Math. Program. 86 (1999), no. 1, Ser. A, 41–50. MR 1712472, DOI 10.1007/s101070050078
- M. Saunders, PDCO: Primal-dual interior method for convex objectives 2002 [Online]. Available: http://www.stanford.edu/group/SOL/software/pdco.html
- Paul Tseng and Sangwoon Yun, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program. 117 (2009), no. 1-2, Ser. B, 387–423. MR 2421312, DOI 10.1007/s10107-007-0170-0
- Joel A. Tropp, Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inform. Theory 50 (2004), no. 10, 2231–2242. MR 2097044, DOI 10.1109/TIT.2004.834793
- Zaiwen Wen, Wotao Yin, Donald Goldfarb, and Yin Zhang, A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation, SIAM J. Sci. Comput. 32 (2010), no. 4, 1832–1857. MR 2678081, DOI 10.1137/090747695
- Zaiwen Wen, Wotao Yin, Hongchao Zhang, and Donald Goldfarb, On the convergence of an active-set method for $\ell _1$ minimization, Optim. Methods Softw. 27 (2012), no. 6, 1127–1146. MR 2955298, DOI 10.1080/10556788.2011.591398
- Stephen J. Wright, Robert D. Nowak, and Mário A. T. Figueiredo, Sparse reconstruction by separable approximation, IEEE Trans. Signal Process. 57 (2009), no. 7, 2479–2493. MR 2650165, DOI 10.1109/TSP.2009.2016892
- Wotao Yin, Stanley Osher, Donald Goldfarb, and Jerome Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci. 1 (2008), no. 1, 143–168. MR 2475828, DOI 10.1137/070703983
- G. X. Yuan, C. H. Ho, and C. J. Lin, Recent advances of large-scale linear classification, Proceedings of the IEEE 100 (2012), 2584–2603.
Additional Information
- Wanyou Cheng
- Affiliation: College of Computer, Dongguan University of Technology, Dongguan 523000, People’s Republic of China
- MR Author ID: 828685
- Email: chengwanyou@sina.com
- Yu-Hong Dai
- Affiliation: LSEC, ICMSEC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, People’s Republic of China
- MR Author ID: 620453
- Email: dyh@lsec.cc.ac.cn
- Received by editor(s): November 28, 2014
- Received by editor(s) in revised form: October 4, 2015, July 30, 2016, and October 23, 2016
- Published electronically: August 3, 2017
- Additional Notes: The authors were supported by the Chinese NSF Grant (nos. 11371154, 11331012 and 81173633), the Key Project of Chinese National Programs for Fundamental Research and Development (no. 2015CB856000), the China National Funds for Distinguished Young Scientists (no. 11125107) and by the Guangdong Province Outstanding Young Teacher Training Program (nos. 3XZ150603 and 2015KTSCX1)
- © Copyright 2017 American Mathematical Society
- Journal: Math. Comp. 87 (2018), 1283-1305
- MSC (2010): Primary 90C06, 90C25, 65Y20, 94A08
- DOI: https://doi.org/10.1090/mcom/3238
- MathSciNet review: 3766388