# American Institute of Mathematical Sciences

February  2015, 9(1): 257-272. doi: 10.3934/ipi.2015.9.257

## A new spectral method for $l_1$-regularized minimization

 1 College of Mathematics and Information Science, Jiangxi Normal University, Nanchang, Jiangxi, China, China

Received  September 2011 Revised  September 2013 Published  January 2015

In this paper, we propose an iterative method for solving the $\ell_1$-regularized minimization problem $\min_{x\in\mathbb{R}^n} f(x)+\rho^T |x|$, which has great applications in the areas of compressive sensing. The construction of our method consists of two main steps: (1) to reformulate an $\ell_1$-problem into a nonsmooth equation $h^\tau(x)={\bf 0}$, where ${\bf 0}\in \mathbb{R}^n$ is the zero vector; and (2) to use $-h^\tau(x)$ as a search direction. The proposed method can be regarded as spectral residual method because we use the residual as a search direction at each iteration. Under mild conditions, we establish the global convergence of the method with a nonmonotone line search. Some numerical experiments are performed to compare the behavior of the proposed method with three other methods. The results positively support the proposed method.
Citation: Lei Wu, Zhe Sun. A new spectral method for $l_1$-regularized minimization. Inverse Problems & Imaging, 2015, 9 (1) : 257-272. doi: 10.3934/ipi.2015.9.257
##### References:
 [1] M. Afonso, J. Bioucas-Dias and M. Figueiredo, Fast image recovery using variable splitting and constrained optimization, IEEE Transactions on Image Processing, 19 (2010), 2345-2356. doi: 10.1109/TIP.2010.2047910.  Google Scholar [2] J. Barzilai and J. Borwein, Two point step size gradient methods, IMA Journal of Numerical Analysis, 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.  Google Scholar [3] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2 (2009), 183-202. doi: 10.1137/080716542.  Google Scholar [4] E. G. Birgin, I. Chambouleyron and J. M. Martínez, Estimation of the optical constants and the thickness of thin fims using unconstrained optimization, Journal of Computational Physics, 151 (1999), 862-880. Google Scholar [5] E. G. Birgin, J. M. Martínez and M. Raydan, Nonmonotone spectral projected gradient methods for convex sets, SIAM Journal on Optimization, 10 (2000), 1196-1211. doi: 10.1137/S1052623497330963.  Google Scholar [6] S. Bonettini, R. Zanella and L. Zanni, A scaled gradient projection method for constrained image deblurring, Inverse Problems, 25 (2009), 015002, 23pp. doi: 10.1088/0266-5611/25/1/015002.  Google Scholar [7] R. H. Byrd, G. M. Chin, J. Nocedal and F. Oztoprak, A Family of Second-order Methods for Convex $l_1$-regularized Optimization, Technical Report, 2012. Available from: http://www.optimization-online.org/DB_HTML/2012/06/3516.html. Google Scholar [8] P. S. Bradley, U. M. Fayyad and O. L. Mangasarian, Mathematical programming for data mining: Formulations and challenges, INFORMS Journal on Computing, 11 (1999), 217-238. doi: 10.1287/ijoc.11.3.217.  Google Scholar [9] X. Chen and W. Zhou, Smoothing nonlinear conjugate gradient method for image restoration using nonsmooth nonconvex minimization, SIAM Journal on Imaging Sciences, 3 (2010), 765-790. doi: 10.1137/080740167.  Google Scholar [10] F. H. Clarke, Optimization and Nonsmooth Analysis, Cambridge University Press, 1990. doi: 10.1137/1.9781611971309.  Google Scholar [11] P. Combettes and V. Wajs, Signal recovery by proximal forwardbackward splitting, SIAM Journal on Modeling and Simulation, 4 (2005), 1168-1200. doi: 10.1137/050626090.  Google Scholar [12] 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 [13] Y. H. Dai and L. Z. Liao, R-linear convergence of the Barzilai and Borwein gradient method, IMA Journal of Numerical Analysis, 22 (2002), 1-10. doi: 10.1093/imanum/22.1.1.  Google Scholar [14] Y. H. Dai, J. Y. Yuan and Y. Yuan, Modified two-point stepsize gradient methods for uncon- strained optimization, Computational Optimization and Applications, 22 (2002), 103-109. doi: 10.1023/A:1014838419611.  Google Scholar [15] Y. H. Dai and Y. Yuan, Alternate minimization gradient method, IMA Journal of Numerical Analysis, 23 (2003), 377-393. doi: 10.1093/imanum/23.3.377.  Google Scholar [16] E. Esser, Applications of Lagrangian-Based Alternating Direction Methods and Connections to Split Bregman, CAM Report 09-31, UCLA, Los Angeles, CA, 2009. Available from: http://www.math.ucla.edu/applied/cam/. Google Scholar [17] 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 [18] R. Fletcher, On the Barzilai-Borwein method, in Optimization and control with applications(eds. L. Qi, L.T. Kok and X. Yang), Springer, New York, 96 (2005), 235-256. doi: 10.1007/0-387-24255-4_10.  Google Scholar [19] M. Fukushima, SOR- and Jacobi-type iterative methods for solving $l_1$-$l_2$ problems by way of Fenchel duality, Optimization Letters, 6 (2012), 679-686. doi: 10.1007/s11590-011-0292-4.  Google Scholar [20] W. Glunt, T. L. Hayden and M. Raydan, Molecular conformations from distance matrices, Journal of Computational Chemistry, 14 (1993), 114-120. doi: 10.1002/jcc.540140115.  Google Scholar [21] T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems, SIAM Journal on Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891.  Google Scholar [22] L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton's method, SIAM Journal on Numerical Analysis, 23 (1986), 707-716. doi: 10.1137/0723046.  Google Scholar [23] W. W. Hager, D. T. Phan and H. Zhang, Gradient-based methods for sparse recovery, SIAM Journal on Imaging Sciences, 4 (2011), 146-165. doi: 10.1137/090775063.  Google Scholar [24] E. T. Hale, W. Yin and Y. Zhang, Fixed-point continuation for $l_1$-minimization: Methodology and convergence, SIAM Journal on Optimization, 19 (2008), 1107-1130. doi: 10.1137/070698920.  Google Scholar [25] W. B. Liu and Y. H. Dai, Minimization algorithms based on supervisor and searcher cooperation, Journal of Optimization Theory and Applications, 111 (2001), 359-379. doi: 10.1023/A:1011986402461.  Google Scholar [26] I. Loris, M. Bertero, C. De Mol, R. Zanella and L. Zanni, Accelerating gradient projection methods for $l_1$-constrained signal recovery by steplength selection rules, Applied and Computational Harmonic Analysis, 27 (2009), 247-254. doi: 10.1016/j.acha.2009.02.003.  Google Scholar [27] L. Qi and J. Sun, A nonsmooth version of Newton's method, Mathematical Programming, 58 (1993), 353-367. doi: 10.1007/BF01581275.  Google Scholar [28] M. Raydan, On the Barzilai and Borwein choice of the steplength for the gradient method, IMA Journal on Numerical Analysis, 13 (1993), 321-326. doi: 10.1093/imanum/13.3.321.  Google Scholar [29] M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM Journal on Optimization, 7 (1997), 26-33. doi: 10.1137/S1052623494266365.  Google Scholar [30] I. Selesnick, R. Van Slyke and O. Guleryuz, Pixel recovery via $l_1$ minimization in the wavelet domain, Proceedings of the 2004 International Conference on Image Processing, 3 (2004), 1819-1822. Google Scholar [31] W. Sun and Y.-X. Yuan, Optimization Theory and Methods: Nonlinear Programming, New York, Springer, 2006.  Google Scholar [32] P. Tseng and S. Yun, A coordinate gradient descent method for nonsmooth separable minimization, Mathematical Programming, 117 (2009), 387-423. doi: 10.1007/s10107-007-0170-0.  Google Scholar [33] Y. Zhang, When Is Missing Data Recoverable?, CAAM Technical report TR06-15, Rice University, Houston, TX, 2006. Available from: http://dsp.rice.edu/cs. Google Scholar [34] S. J. Wright, R. Nowak and M. Figueiredo, Sparse reconstruction by separable approximation, IEEE Transactions on Signal Processing, 57 (2009), 2479-2493. doi: 10.1109/TSP.2009.2016892.  Google Scholar [35] J. Xu and S. Osher, Iterative regularization and nonlinear inverse scale space applied to wavelet-based denoising, IEEE Transation on Image Processing, 16 (2007), 534-544. doi: 10.1109/TIP.2006.888335.  Google Scholar [36] W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM Journal on Imaging Sciences, 1 (2008), 143-168. doi: 10.1137/070703983.  Google Scholar [37] S. Yun and K.-C. Toh, A coordinate gradient descent method for $l_1$-regularized convex minimization, Computational Optimization and Applications, 48 (2011), 273-307. doi: 10.1007/s10589-009-9251-8.  Google Scholar [38] J. Yang and Y. Zhang, Alternating direction algorithms for $l_1$ problems in compressive sensing, SIAM Journal on Scientific Computing, 33 (2011), 250-278. doi: 10.1137/090777761.  Google Scholar

show all references

##### References:
 [1] M. Afonso, J. Bioucas-Dias and M. Figueiredo, Fast image recovery using variable splitting and constrained optimization, IEEE Transactions on Image Processing, 19 (2010), 2345-2356. doi: 10.1109/TIP.2010.2047910.  Google Scholar [2] J. Barzilai and J. Borwein, Two point step size gradient methods, IMA Journal of Numerical Analysis, 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.  Google Scholar [3] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2 (2009), 183-202. doi: 10.1137/080716542.  Google Scholar [4] E. G. Birgin, I. Chambouleyron and J. M. Martínez, Estimation of the optical constants and the thickness of thin fims using unconstrained optimization, Journal of Computational Physics, 151 (1999), 862-880. Google Scholar [5] E. G. Birgin, J. M. Martínez and M. Raydan, Nonmonotone spectral projected gradient methods for convex sets, SIAM Journal on Optimization, 10 (2000), 1196-1211. doi: 10.1137/S1052623497330963.  Google Scholar [6] S. Bonettini, R. Zanella and L. Zanni, A scaled gradient projection method for constrained image deblurring, Inverse Problems, 25 (2009), 015002, 23pp. doi: 10.1088/0266-5611/25/1/015002.  Google Scholar [7] R. H. Byrd, G. M. Chin, J. Nocedal and F. Oztoprak, A Family of Second-order Methods for Convex $l_1$-regularized Optimization, Technical Report, 2012. Available from: http://www.optimization-online.org/DB_HTML/2012/06/3516.html. Google Scholar [8] P. S. Bradley, U. M. Fayyad and O. L. Mangasarian, Mathematical programming for data mining: Formulations and challenges, INFORMS Journal on Computing, 11 (1999), 217-238. doi: 10.1287/ijoc.11.3.217.  Google Scholar [9] X. Chen and W. Zhou, Smoothing nonlinear conjugate gradient method for image restoration using nonsmooth nonconvex minimization, SIAM Journal on Imaging Sciences, 3 (2010), 765-790. doi: 10.1137/080740167.  Google Scholar [10] F. H. Clarke, Optimization and Nonsmooth Analysis, Cambridge University Press, 1990. doi: 10.1137/1.9781611971309.  Google Scholar [11] P. Combettes and V. Wajs, Signal recovery by proximal forwardbackward splitting, SIAM Journal on Modeling and Simulation, 4 (2005), 1168-1200. doi: 10.1137/050626090.  Google Scholar [12] 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 [13] Y. H. Dai and L. Z. Liao, R-linear convergence of the Barzilai and Borwein gradient method, IMA Journal of Numerical Analysis, 22 (2002), 1-10. doi: 10.1093/imanum/22.1.1.  Google Scholar [14] Y. H. Dai, J. Y. Yuan and Y. Yuan, Modified two-point stepsize gradient methods for uncon- strained optimization, Computational Optimization and Applications, 22 (2002), 103-109. doi: 10.1023/A:1014838419611.  Google Scholar [15] Y. H. Dai and Y. Yuan, Alternate minimization gradient method, IMA Journal of Numerical Analysis, 23 (2003), 377-393. doi: 10.1093/imanum/23.3.377.  Google Scholar [16] E. Esser, Applications of Lagrangian-Based Alternating Direction Methods and Connections to Split Bregman, CAM Report 09-31, UCLA, Los Angeles, CA, 2009. Available from: http://www.math.ucla.edu/applied/cam/. Google Scholar [17] 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 [18] R. Fletcher, On the Barzilai-Borwein method, in Optimization and control with applications(eds. L. Qi, L.T. Kok and X. Yang), Springer, New York, 96 (2005), 235-256. doi: 10.1007/0-387-24255-4_10.  Google Scholar [19] M. Fukushima, SOR- and Jacobi-type iterative methods for solving $l_1$-$l_2$ problems by way of Fenchel duality, Optimization Letters, 6 (2012), 679-686. doi: 10.1007/s11590-011-0292-4.  Google Scholar [20] W. Glunt, T. L. Hayden and M. Raydan, Molecular conformations from distance matrices, Journal of Computational Chemistry, 14 (1993), 114-120. doi: 10.1002/jcc.540140115.  Google Scholar [21] T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems, SIAM Journal on Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891.  Google Scholar [22] L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton's method, SIAM Journal on Numerical Analysis, 23 (1986), 707-716. doi: 10.1137/0723046.  Google Scholar [23] W. W. Hager, D. T. Phan and H. Zhang, Gradient-based methods for sparse recovery, SIAM Journal on Imaging Sciences, 4 (2011), 146-165. doi: 10.1137/090775063.  Google Scholar [24] E. T. Hale, W. Yin and Y. Zhang, Fixed-point continuation for $l_1$-minimization: Methodology and convergence, SIAM Journal on Optimization, 19 (2008), 1107-1130. doi: 10.1137/070698920.  Google Scholar [25] W. B. Liu and Y. H. Dai, Minimization algorithms based on supervisor and searcher cooperation, Journal of Optimization Theory and Applications, 111 (2001), 359-379. doi: 10.1023/A:1011986402461.  Google Scholar [26] I. Loris, M. Bertero, C. De Mol, R. Zanella and L. Zanni, Accelerating gradient projection methods for $l_1$-constrained signal recovery by steplength selection rules, Applied and Computational Harmonic Analysis, 27 (2009), 247-254. doi: 10.1016/j.acha.2009.02.003.  Google Scholar [27] L. Qi and J. Sun, A nonsmooth version of Newton's method, Mathematical Programming, 58 (1993), 353-367. doi: 10.1007/BF01581275.  Google Scholar [28] M. Raydan, On the Barzilai and Borwein choice of the steplength for the gradient method, IMA Journal on Numerical Analysis, 13 (1993), 321-326. doi: 10.1093/imanum/13.3.321.  Google Scholar [29] M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM Journal on Optimization, 7 (1997), 26-33. doi: 10.1137/S1052623494266365.  Google Scholar [30] I. Selesnick, R. Van Slyke and O. Guleryuz, Pixel recovery via $l_1$ minimization in the wavelet domain, Proceedings of the 2004 International Conference on Image Processing, 3 (2004), 1819-1822. Google Scholar [31] W. Sun and Y.-X. Yuan, Optimization Theory and Methods: Nonlinear Programming, New York, Springer, 2006.  Google Scholar [32] P. Tseng and S. Yun, A coordinate gradient descent method for nonsmooth separable minimization, Mathematical Programming, 117 (2009), 387-423. doi: 10.1007/s10107-007-0170-0.  Google Scholar [33] Y. Zhang, When Is Missing Data Recoverable?, CAAM Technical report TR06-15, Rice University, Houston, TX, 2006. Available from: http://dsp.rice.edu/cs. Google Scholar [34] S. J. Wright, R. Nowak and M. Figueiredo, Sparse reconstruction by separable approximation, IEEE Transactions on Signal Processing, 57 (2009), 2479-2493. doi: 10.1109/TSP.2009.2016892.  Google Scholar [35] J. Xu and S. Osher, Iterative regularization and nonlinear inverse scale space applied to wavelet-based denoising, IEEE Transation on Image Processing, 16 (2007), 534-544. doi: 10.1109/TIP.2006.888335.  Google Scholar [36] W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM Journal on Imaging Sciences, 1 (2008), 143-168. doi: 10.1137/070703983.  Google Scholar [37] S. Yun and K.-C. Toh, A coordinate gradient descent method for $l_1$-regularized convex minimization, Computational Optimization and Applications, 48 (2011), 273-307. doi: 10.1007/s10589-009-9251-8.  Google Scholar [38] J. Yang and Y. Zhang, Alternating direction algorithms for $l_1$ problems in compressive sensing, SIAM Journal on Scientific Computing, 33 (2011), 250-278. doi: 10.1137/090777761.  Google Scholar
 [1] Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems & Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487 [2] Z.Y. Wu, H.W.J. Lee, F.S. Bai, L.S. Zhang. Quadratic smoothing approximation to $l_1$ exact penalty function in global optimization. Journal of Industrial & Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533 [3] Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems & Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761 [4] Steven L. Brunton, Joshua L. Proctor, Jonathan H. Tu, J. Nathan Kutz. Compressed sensing and dynamic mode decomposition. Journal of Computational Dynamics, 2015, 2 (2) : 165-191. doi: 10.3934/jcd.2015002 [5] Burak Ordin, Adil Bagirov, Ehsan Mohebi. An incremental nonsmooth optimization algorithm for clustering using $L_1$ and $L_\infty$ norms. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2757-2779. doi: 10.3934/jimo.2019079 [6] Gautier Picot. Energy-minimal transfers in the vicinity of the lagrangian point $L_1$. Conference Publications, 2011, 2011 (Special) : 1196-1205. doi: 10.3934/proc.2011.2011.1196 [7] Yingying Li, Stanley Osher, Richard Tsai. Heat source identification based on $l_1$ constrained minimization. Inverse Problems & Imaging, 2014, 8 (1) : 199-221. doi: 10.3934/ipi.2014.8.199 [8] Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1519-1526. doi: 10.3934/jimo.2019014 [9] Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949 [10] Satoshi Ito, Soon-Yi Wu, Ting-Jang Shiu, Kok Lay Teo. A numerical approach to infinite-dimensional linear programming in $L_1$ spaces. Journal of Industrial & Management Optimization, 2010, 6 (1) : 15-28. doi: 10.3934/jimo.2010.6.15 [11] Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $l_1$ norm measure. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2425-2437. doi: 10.3934/jimo.2019061 [12] Zhaohui Guo, Stanley Osher. Template matching via $l_1$ minimization and its application to hyperspectral data. Inverse Problems & Imaging, 2011, 5 (1) : 19-35. doi: 10.3934/ipi.2011.5.19 [13] Yupeng Li, Wuchen Li, Guo Cao. Image segmentation via $L_1$ Monge-Kantorovich problem. Inverse Problems & Imaging, 2019, 13 (4) : 805-826. doi: 10.3934/ipi.2019037 [14] Jiying Liu, Jubo Zhu, Fengxia Yan, Zenghui Zhang. Compressive sampling and $l_1$ minimization for SAR imaging with low sampling rate. Inverse Problems & Imaging, 2013, 7 (4) : 1295-1305. doi: 10.3934/ipi.2013.7.1295 [15] Vladimir Gaitsgory, Tanya Tarnopolskaya. Threshold value of the penalty parameter in the minimization of $L_1$-penalized conditional value-at-risk. Journal of Industrial & Management Optimization, 2013, 9 (1) : 191-204. doi: 10.3934/jimo.2013.9.191 [16] Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075 [17] Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283 [18] Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171 [19] Zhongliang Deng, Enwen Hu. Error minimization with global optimization for difference of convex functions. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1027-1033. doi: 10.3934/dcdss.2019070 [20] Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial & Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117

2020 Impact Factor: 1.639