Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

Gradient-based method with active set strategy for $ \ell_1$ optimization


Authors: Wanyou Cheng and Yu-Hong Dai
Journal: Math. Comp.
MSC (2010): Primary 90C06, 90C25, 65Y20, 94A08
DOI: https://doi.org/10.1090/mcom/3238
Published electronically: August 3, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1109/TIP.2010.2047910
  • [2] 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, https://doi.org/10.1137/090762294
  • [3] 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, https://doi.org/10.1137/100786721
  • [4] Jonathan Barzilai and Jonathan M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal. 8 (1988), no. 1, 141-148. MR 967848, https://doi.org/10.1093/imanum/8.1.141
  • [5] 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, https://doi.org/10.1137/080716542
  • [6] 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, https://doi.org/10.1137/120869778
  • [7] 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, https://doi.org/10.1109/TIP.2007.909319
  • [8] 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 (electronic). MR 1777088, https://doi.org/10.1137/S1052623497330963
  • [9] 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, https://doi.org/10.1137/120878951
  • [10] 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, https://doi.org/10.1137/060657704
  • [11] 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, https://doi.org/10.1137/0725068
  • [12] 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/
  • [13] Wanyou Cheng and Zixin Chen, Nonmonotone spectral method for large-scale symmetric nonlinear equations, Numer. Algorithms 62 (2013), no. 1, 149-162. MR 3009560, https://doi.org/10.1007/s11075-012-9572-z
  • [14] Y. H. Dai, A new analysis on the Barzilai-Borwein gradient method, J. Oper. Res. Soc. China. 1 (2013), pp. 187-198.
  • [15] 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, https://doi.org/10.1007/s00211-004-0569-y
  • [16] 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, https://doi.org/10.1093/imanum/drl006
  • [17] 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, https://doi.org/10.1093/imanum/22.1.1
  • [18] 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, https://doi.org/10.1002/cpa.20042
  • [19] G. Davis, S. Mallat, and M. Avellaneda, Adaptive greedy approximations, Constr. Approx. 13 (1997), no. 1, 57-98. MR 1424364, https://doi.org/10.1007/s003659900033
  • [20] David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289-1306. MR 2241189, https://doi.org/10.1109/TIT.2006.871582
  • [21] 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, https://doi.org/10.1109/TIT.2005.860430
  • [22] 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, https://doi.org/10.1007/s101070100263
  • [23] 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, https://doi.org/10.1016/j.acha.2007.02.002
  • [24] 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, https://doi.org/10.1109/TIP.2003.814255
  • [25] 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.
  • [26] 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, https://doi.org/10.1007/s10107-015-0875-4
  • [27] 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, https://doi.org/10.1137/0723046
  • [28] 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, https://doi.org/10.1137/070698920
  • [29] 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, https://doi.org/10.1137/090775063
  • [30] 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.
  • [31] 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
  • [32] 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
  • [33] R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, NJ, 1970. MR 0274683
  • [34] 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, https://doi.org/10.1007/s101070050078
  • [35] M. Saunders, PDCO: Primal-dual interior method for convex objectives 2002 [Online]. Available: http://www.stanford.edu/group/SOL/software/pdco.html
  • [36] 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, https://doi.org/10.1007/s10107-007-0170-0
  • [37] Joel A. Tropp, Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inform. Theory 50 (2004), no. 10, 2231-2242. MR 2097044, https://doi.org/10.1109/TIT.2004.834793
  • [38] 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, https://doi.org/10.1137/090747695
  • [39] 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, https://doi.org/10.1080/10556788.2011.591398
  • [40] 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, https://doi.org/10.1109/TSP.2009.2016892
  • [41] 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, https://doi.org/10.1137/070703983
  • [42] 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.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 90C06, 90C25, 65Y20, 94A08

Retrieve articles in all journals with MSC (2010): 90C06, 90C25, 65Y20, 94A08


Additional Information

Wanyou Cheng
Affiliation: College of Computer, Dongguan University of Technology, Dongguan 523000, People’s Republic of China
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
Email: dyh@lsec.cc.ac.cn

DOI: https://doi.org/10.1090/mcom/3238
Keywords: $\ell_1$ minimization, compressive sensing, active set, Barzilai-Borwein method
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)
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society