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 and 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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[10]

F. H. Clarke, Optimization and Nonsmooth Analysis, Cambridge University Press, 1990. doi: 10.1137/1.9781611971309.

[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.

[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.

[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.

[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.

[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.

[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/.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[27]

L. Qi and J. Sun, A nonsmooth version of Newton's method, Mathematical Programming, 58 (1993), 353-367. doi: 10.1007/BF01581275.

[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.

[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.

[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.

[31]

W. Sun and Y.-X. Yuan, Optimization Theory and Methods: Nonlinear Programming, New York, Springer, 2006.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[10]

F. H. Clarke, Optimization and Nonsmooth Analysis, Cambridge University Press, 1990. doi: 10.1137/1.9781611971309.

[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.

[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.

[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.

[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.

[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.

[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/.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[27]

L. Qi and J. Sun, A nonsmooth version of Newton's method, Mathematical Programming, 58 (1993), 353-367. doi: 10.1007/BF01581275.

[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.

[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.

[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.

[31]

W. Sun and Y.-X. Yuan, Optimization Theory and Methods: Nonlinear Programming, New York, Springer, 2006.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[1]

Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and 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 and 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 and Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761

[4]

Lican Kang, Yuan Luo, Jerry Zhijian Yang, Chang Zhu. A primal and dual active set algorithm for truncated $L_1$ regularized logistic regression. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022050

[5]

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

[6]

Burak Ordin, Adil Bagirov, Ehsan Mohebi. An incremental nonsmooth optimization algorithm for clustering using $ L_1 $ and $ L_\infty $ norms. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2757-2779. doi: 10.3934/jimo.2019079

[7]

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

[8]

Yingying Li, Stanley Osher, Richard Tsai. Heat source identification based on $l_1$ constrained minimization. Inverse Problems and Imaging, 2014, 8 (1) : 199-221. doi: 10.3934/ipi.2014.8.199

[9]

Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1519-1526. doi: 10.3934/jimo.2019014

[10]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial and Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949

[11]

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 and Management Optimization, 2010, 6 (1) : 15-28. doi: 10.3934/jimo.2010.6.15

[12]

Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2425-2437. doi: 10.3934/jimo.2019061

[13]

Zhaohui Guo, Stanley Osher. Template matching via $l_1$ minimization and its application to hyperspectral data. Inverse Problems and Imaging, 2011, 5 (1) : 19-35. doi: 10.3934/ipi.2011.5.19

[14]

Yupeng Li, Wuchen Li, Guo Cao. Image segmentation via $ L_1 $ Monge-Kantorovich problem. Inverse Problems and Imaging, 2019, 13 (4) : 805-826. doi: 10.3934/ipi.2019037

[15]

Jiying Liu, Jubo Zhu, Fengxia Yan, Zenghui Zhang. Compressive sampling and $l_1$ minimization for SAR imaging with low sampling rate. Inverse Problems and Imaging, 2013, 7 (4) : 1295-1305. doi: 10.3934/ipi.2013.7.1295

[16]

Vladimir Gaitsgory, Tanya Tarnopolskaya. Threshold value of the penalty parameter in the minimization of $L_1$-penalized conditional value-at-risk. Journal of Industrial and Management Optimization, 2013, 9 (1) : 191-204. doi: 10.3934/jimo.2013.9.191

[17]

Zohre Aminifard, Saman Babaie-Kafaki. Diagonally scaled memoryless quasi–Newton methods with application to compressed sensing. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021191

[18]

Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075

[19]

Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283

[20]

Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171

2020 Impact Factor: 1.639

Metrics

  • PDF downloads (124)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]