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.  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.  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.  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.   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.  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).  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).   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.  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.  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.  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.  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.  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.  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.  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, (2009), 09.   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.  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, 96 (2005), 235.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.   Google Scholar

[31]

W. Sun and Y.-X. Yuan, Optimization Theory and Methods: Nonlinear Programming,, New York, (2006).   Google Scholar

[32]

P. Tseng and S. Yun, A coordinate gradient descent method for nonsmooth separable minimization,, Mathematical Programming, 117 (2009), 387.  doi: 10.1007/s10107-007-0170-0.  Google Scholar

[33]

Y. Zhang, When Is Missing Data Recoverable?,, CAAM Technical report TR06-15, (2006), 06.   Google Scholar

[34]

S. J. Wright, R. Nowak and M. Figueiredo, Sparse reconstruction by separable approximation,, IEEE Transactions on Signal Processing, 57 (2009), 2479.  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.  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.  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.  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.  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.  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.  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.  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.   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.  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).  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).   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.  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.  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.  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.  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.  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.  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.  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, (2009), 09.   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.  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, 96 (2005), 235.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.   Google Scholar

[31]

W. Sun and Y.-X. Yuan, Optimization Theory and Methods: Nonlinear Programming,, New York, (2006).   Google Scholar

[32]

P. Tseng and S. Yun, A coordinate gradient descent method for nonsmooth separable minimization,, Mathematical Programming, 117 (2009), 387.  doi: 10.1007/s10107-007-0170-0.  Google Scholar

[33]

Y. Zhang, When Is Missing Data Recoverable?,, CAAM Technical report TR06-15, (2006), 06.   Google Scholar

[34]

S. J. Wright, R. Nowak and M. Figueiredo, Sparse reconstruction by separable approximation,, IEEE Transactions on Signal Processing, 57 (2009), 2479.  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.  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.  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.  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.  doi: 10.1137/090777761.  Google Scholar

[1]

Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 741-753. doi: 10.3934/dcdsb.2020139

[2]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[3]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100

[4]

El Haj Laamri, Michel Pierre. Stationary reaction-diffusion systems in $ L^1 $ revisited. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 455-464. doi: 10.3934/dcdss.2020355

[5]

Waixiang Cao, Lueling Jia, Zhimin Zhang. A $ C^1 $ Petrov-Galerkin method and Gauss collocation method for 1D general elliptic problems and superconvergence. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 81-105. doi: 10.3934/dcdsb.2020327

[6]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[7]

Hedy Attouch, Aïcha Balhag, Zaki Chbani, Hassan Riahi. Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021010

[8]

C. J. Price. A modified Nelder-Mead barrier method for constrained optimization. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020058

[9]

Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135

[10]

Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021006

[11]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101

[12]

Oussama Landoulsi. Construction of a solitary wave solution of the nonlinear focusing schrödinger equation outside a strictly convex obstacle in the $ L^2 $-supercritical case. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 701-746. doi: 10.3934/dcds.2020298

[13]

Ziang Long, Penghang Yin, Jack Xin. Global convergence and geometric characterization of slow to fast weight evolution in neural network training for classifying linearly non-separable data. Inverse Problems & Imaging, 2021, 15 (1) : 41-62. doi: 10.3934/ipi.2020077

[14]

Hua Qiu, Zheng-An Yao. The regularized Boussinesq equations with partial dissipations in dimension two. Electronic Research Archive, 2020, 28 (4) : 1375-1393. doi: 10.3934/era.2020073

[15]

Kung-Ching Chang, Xuefeng Wang, Xie Wu. On the spectral theory of positive operators and PDE applications. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3171-3200. doi: 10.3934/dcds.2020054

[16]

Joel Kübler, Tobias Weth. Spectral asymptotics of radial solutions and nonradial bifurcation for the Hénon equation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3629-3656. doi: 10.3934/dcds.2020032

[17]

Bopeng Rao, Zhuangyi Liu. A spectral approach to the indirect boundary control of a system of weakly coupled wave equations. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 399-414. doi: 10.3934/dcds.2009.23.399

[18]

Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020389

[19]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003

[20]

Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1

2019 Impact Factor: 1.373

Metrics

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

Other articles
by authors

[Back to Top]