August  2015, 9(3): 815-833. doi: 10.3934/ipi.2015.9.815

Nomonotone spectral gradient method for sparse recovery

1. 

College of Computer, Dongguan University of Technology, Dongguan, 523000, China, China

2. 

School of Mathematical Sciences, South China Normal University, Guangzhou, 510631, China

Received  May 2014 Revised  September 2014 Published  July 2015

In the paper, we present an algorithm framework for the more general problem of minimizing the sum $f(x)+\psi(x)$, where $f$ is smooth and $\psi$ is convex, but possible nonsmooth. At each step, the search direction of the algorithm is obtained by solving an optimization problem involving a quadratic term with diagonal Hessian and Barzilai-Borwein steplength plus $ \psi(x)$. The nonmonotone strategy is combined with -Borwein steplength to accelerate the convergence process. The method with the nomonotone line search techniques is showed to be globally convergent. In particular, if $f$ is convex, we show that the method shares a sublinear global rate of convergence. Moreover, if $f$ is strongly convex, we prove that the method converges R-linearly. Numerical experiments with compressive sense problems show that our approach is competitive with several known methods for some standard $l_2-l_1$ problems.
Citation: Wanyou Cheng, Zixin Chen, Donghui Li. Nomonotone spectral gradient method for sparse recovery. Inverse Problems and Imaging, 2015, 9 (3) : 815-833. doi: 10.3934/ipi.2015.9.815
References:
[1]

M. Afonso, J. Bioucas-Dias and M. Figueiredo, Fast image recovery using variable splitting and constrained optimization, IEEE Trans. Image Process., 19 (2010), 2345-2356. doi: 10.1109/TIP.2010.2047910.

[2]

S. Aybat and G. Iyengar, A first-order smoothed penalty method for compressed sensing, SIAM J. Optim., 21 (2011), 287-313. doi: 10.1137/090762294.

[3]

J. Barzilai and J. M. Borwein, Two point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.

[4]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), 183-202. doi: 10.1137/080716542.

[5]

A. Beck and Y. C. Eldar, Sparsity constrained nonlinear optimization: Optimality conditions and algorithms, SIAM J. Optim., 23 (2013), 1480-1509. doi: 10.1137/120869778.

[6]

J. M. Bioucas-Dias and M. A. T. Figueiredo, A new TwIST: Two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Trans. Image Process., 16 (2007), 2992-3004. doi: 10.1109/TIP.2007.909319.

[7]

E. G. Birgin, J. M. Martínez and M. Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., 10 (2000), 1196-1121. doi: 10.1137/S1052623497330963.

[8]

D. Boley, Local linear convergence of the alternating direction method of multipliers on quadratic or linear program, SIAM J. Optim., 23 (2013), 2183-2207. doi: 10.1137/120878951.

[9]

A. M. Bruckstein, D. L. Donoho and M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51 (2009), 34-81. doi: 10.1137/060657704.

[10]

E. Candes and J. Romberg, $l_1$-magic: A collection of MATLAB Routines for Solving the Convex Optimization Programs Central to Compressive Sampling 2006 [Online]., Available from: , (). 

[11]

W. Y. Cheng and Z. X. Chen, Nonmonotone spectral method for large-scale symmetric nonlinear equations, Numer Algor., 62 (2013), 149-162. doi: 10.1007/s11075-012-9572-z.

[12]

I. Daubechies, M. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57 (2004), 1413-1457. doi: 10.1002/cpa.20042.

[13]

Y.-H. Dai and R. Fletcher, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming, Numer. Math., 100 (2005), 21-47. doi: 10.1007/s00211-004-0569-y.

[14]

Y.-H. Dai, W. W. Hager, K. Schittkowski and H. Zhang, The cyclic Barzilar-Borwein method for unconstrained optimization, IMA J. Numer. Anal., 26 (2006), 604-627. doi: 10.1093/imanum/drl006.

[15]

G. Davis, S. Mallat and M. Avellaneda, Greedy adaptive approximation, Constr Approx., 13 (1997), 57-98. doi: 10.1007/BF02678430.

[16]

D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.

[17]

D. Donoho, M. Elad and V. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Inform. Theory, 52 (2006), 6-18. doi: 10.1109/TIT.2005.860430.

[18]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), 201-213. doi: 10.1007/s101070100263.

[19]

M. Elad, B. Matalon and M. Zibulevsky, Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization, Appl. Comput. Harmon. Anal., 23 (2007), 346-367. doi: 10.1016/j.acha.2007.02.002.

[20]

M. Fukushima and H. Mine, A generalized proximal point algorithm for certain non-convex minimization problems, Int. J. Syst. Sci., 12 (1981), 989-1000. doi: 10.1080/00207728108963798.

[21]

M. A. T. Figueiredo and R. D. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process., 12 (2003), 906-916. doi: 10.1109/TIP.2003.814255.

[22]

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), 586-597. doi: 10.1109/JSTSP.2007.910281.

[23]

M. Fukushima, A successive quadratic programming method for a class of constrained nonsmooth optimization problems,, Math. Program., 49 (): 231.  doi: 10.1007/BF01588789.

[24]

L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal., 23 (1986), 707-716. doi: 10.1137/0723046.

[25]

E. T. Hale, W. Yin and Y. Zhang, Fixed-point continuation for $l_1$ minimization: Methodology and convergence, SIAM J. Optim., 19 (2008), 1107-1130. doi: 10.1137/070698920.

[26]

W. W. Hager, D. T. Phan and H. Zhang, Gradient-based methods for sparse recovery, SIAM J. Imaging Sci., 4 (2011), 146-165. doi: 10.1137/090775063.

[27]

K. C. Kiwiel, A method for minimizing the sum of a convex function and a continuously differentiable function, J. Optim. Theory Appl., 48 (1986), 437-449. doi: 10.1007/BF00940570.

[28]

S. J. Kim, K. Koh, M. Lustig, S. Boyd and D. Gorinevsky, An interior-point method for large-scale $l_1$-regularized least squares, IEEE J. Sel. Top. Signal Process., 1 (2007), 606-617.

[29]

H. Mine and M. Fukushima, A minimization method for the sum of a convex function and a continuously differentiable function, J. Optim. Theory Appl., 33 (1981), 9-23. doi: 10.1007/BF00935173.

[30]

Y. Nesterov, Gradient methods for minimizing composite objective function, 2007, CORE Discussion Paper 2007/76 [Online]. Available from: http://www.optimization-online.org/DB_HTML/2007/09/1784.html.

[31]

R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, NJ, 1970.

[32]

S. M. Robinson, Linear convergence of $\epsilon$-subgradient descent methods for a class of convex functions, Math. Program., 86 (1999), 41-50. doi: 10.1007/s101070050078.

[33]

M. Saunders, PDCO: Primal-Dual Interior Method for Convex Objectives 2002 [Online]., Available from: , (). 

[34]

P. Tseng and S. W. Yun, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program., 117 (2009), 387-423. doi: 10.1007/s10107-007-0170-0.

[35]

J. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Inform. Theory, 50 (2006), 2231-2342. doi: 10.1109/TIT.2004.834793.

[36]

Z. W. Wen, W. T. Yin, D. Goldfarb and Y. Zhang, A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation, SIAM J. Sci. Comput., 32 (2010), 1832-1857. doi: 10.1137/090747695.

[37]

Z. W. Wen, W. T. Yin, H. Zhang and D. Goldfarb, On the convergence of an active-set method for $l_1$ minimization, Optim. Methods Softw., 27 (2012), 1127-1146. doi: 10.1080/10556788.2011.591398.

[38]

J. Wright, R. D. Nowak and M. A. T. Figueiredo, Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57 (2009), 2479-2493. doi: 10.1109/TSP.2009.2016892.

[39]

W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1 (2008), 143-168. doi: 10.1137/070703983.

show all references

References:
[1]

M. Afonso, J. Bioucas-Dias and M. Figueiredo, Fast image recovery using variable splitting and constrained optimization, IEEE Trans. Image Process., 19 (2010), 2345-2356. doi: 10.1109/TIP.2010.2047910.

[2]

S. Aybat and G. Iyengar, A first-order smoothed penalty method for compressed sensing, SIAM J. Optim., 21 (2011), 287-313. doi: 10.1137/090762294.

[3]

J. Barzilai and J. M. Borwein, Two point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.

[4]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), 183-202. doi: 10.1137/080716542.

[5]

A. Beck and Y. C. Eldar, Sparsity constrained nonlinear optimization: Optimality conditions and algorithms, SIAM J. Optim., 23 (2013), 1480-1509. doi: 10.1137/120869778.

[6]

J. M. Bioucas-Dias and M. A. T. Figueiredo, A new TwIST: Two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Trans. Image Process., 16 (2007), 2992-3004. doi: 10.1109/TIP.2007.909319.

[7]

E. G. Birgin, J. M. Martínez and M. Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., 10 (2000), 1196-1121. doi: 10.1137/S1052623497330963.

[8]

D. Boley, Local linear convergence of the alternating direction method of multipliers on quadratic or linear program, SIAM J. Optim., 23 (2013), 2183-2207. doi: 10.1137/120878951.

[9]

A. M. Bruckstein, D. L. Donoho and M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51 (2009), 34-81. doi: 10.1137/060657704.

[10]

E. Candes and J. Romberg, $l_1$-magic: A collection of MATLAB Routines for Solving the Convex Optimization Programs Central to Compressive Sampling 2006 [Online]., Available from: , (). 

[11]

W. Y. Cheng and Z. X. Chen, Nonmonotone spectral method for large-scale symmetric nonlinear equations, Numer Algor., 62 (2013), 149-162. doi: 10.1007/s11075-012-9572-z.

[12]

I. Daubechies, M. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57 (2004), 1413-1457. doi: 10.1002/cpa.20042.

[13]

Y.-H. Dai and R. Fletcher, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming, Numer. Math., 100 (2005), 21-47. doi: 10.1007/s00211-004-0569-y.

[14]

Y.-H. Dai, W. W. Hager, K. Schittkowski and H. Zhang, The cyclic Barzilar-Borwein method for unconstrained optimization, IMA J. Numer. Anal., 26 (2006), 604-627. doi: 10.1093/imanum/drl006.

[15]

G. Davis, S. Mallat and M. Avellaneda, Greedy adaptive approximation, Constr Approx., 13 (1997), 57-98. doi: 10.1007/BF02678430.

[16]

D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.

[17]

D. Donoho, M. Elad and V. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Inform. Theory, 52 (2006), 6-18. doi: 10.1109/TIT.2005.860430.

[18]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), 201-213. doi: 10.1007/s101070100263.

[19]

M. Elad, B. Matalon and M. Zibulevsky, Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization, Appl. Comput. Harmon. Anal., 23 (2007), 346-367. doi: 10.1016/j.acha.2007.02.002.

[20]

M. Fukushima and H. Mine, A generalized proximal point algorithm for certain non-convex minimization problems, Int. J. Syst. Sci., 12 (1981), 989-1000. doi: 10.1080/00207728108963798.

[21]

M. A. T. Figueiredo and R. D. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process., 12 (2003), 906-916. doi: 10.1109/TIP.2003.814255.

[22]

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), 586-597. doi: 10.1109/JSTSP.2007.910281.

[23]

M. Fukushima, A successive quadratic programming method for a class of constrained nonsmooth optimization problems,, Math. Program., 49 (): 231.  doi: 10.1007/BF01588789.

[24]

L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal., 23 (1986), 707-716. doi: 10.1137/0723046.

[25]

E. T. Hale, W. Yin and Y. Zhang, Fixed-point continuation for $l_1$ minimization: Methodology and convergence, SIAM J. Optim., 19 (2008), 1107-1130. doi: 10.1137/070698920.

[26]

W. W. Hager, D. T. Phan and H. Zhang, Gradient-based methods for sparse recovery, SIAM J. Imaging Sci., 4 (2011), 146-165. doi: 10.1137/090775063.

[27]

K. C. Kiwiel, A method for minimizing the sum of a convex function and a continuously differentiable function, J. Optim. Theory Appl., 48 (1986), 437-449. doi: 10.1007/BF00940570.

[28]

S. J. Kim, K. Koh, M. Lustig, S. Boyd and D. Gorinevsky, An interior-point method for large-scale $l_1$-regularized least squares, IEEE J. Sel. Top. Signal Process., 1 (2007), 606-617.

[29]

H. Mine and M. Fukushima, A minimization method for the sum of a convex function and a continuously differentiable function, J. Optim. Theory Appl., 33 (1981), 9-23. doi: 10.1007/BF00935173.

[30]

Y. Nesterov, Gradient methods for minimizing composite objective function, 2007, CORE Discussion Paper 2007/76 [Online]. Available from: http://www.optimization-online.org/DB_HTML/2007/09/1784.html.

[31]

R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, NJ, 1970.

[32]

S. M. Robinson, Linear convergence of $\epsilon$-subgradient descent methods for a class of convex functions, Math. Program., 86 (1999), 41-50. doi: 10.1007/s101070050078.

[33]

M. Saunders, PDCO: Primal-Dual Interior Method for Convex Objectives 2002 [Online]., Available from: , (). 

[34]

P. Tseng and S. W. Yun, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program., 117 (2009), 387-423. doi: 10.1007/s10107-007-0170-0.

[35]

J. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Inform. Theory, 50 (2006), 2231-2342. doi: 10.1109/TIT.2004.834793.

[36]

Z. W. Wen, W. T. Yin, D. Goldfarb and Y. Zhang, A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation, SIAM J. Sci. Comput., 32 (2010), 1832-1857. doi: 10.1137/090747695.

[37]

Z. W. Wen, W. T. Yin, H. Zhang and D. Goldfarb, On the convergence of an active-set method for $l_1$ minimization, Optim. Methods Softw., 27 (2012), 1127-1146. doi: 10.1080/10556788.2011.591398.

[38]

J. Wright, R. D. Nowak and M. A. T. Figueiredo, Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57 (2009), 2479-2493. doi: 10.1109/TSP.2009.2016892.

[39]

W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1 (2008), 143-168. doi: 10.1137/070703983.

[1]

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

[2]

Lican Kang, Yanming Lai, Yanyan Liu, Yuan Luo, Jing Zhang. High-dimensional linear regression with hard thresholding regularization: Theory and algorithm. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022034

[3]

Huan Gao, Yu-Hong Dai, Xiao-Jiao Tong. Barzilai-Borwein-like methods for the extreme eigenvalue problem. Journal of Industrial and Management Optimization, 2015, 11 (3) : 999-1019. doi: 10.3934/jimo.2015.11.999

[4]

Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79

[5]

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

[6]

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

[7]

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

[8]

A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial and Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319

[9]

Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859

[10]

Jueyou Li, Guoquan Li, Zhiyou Wu, Changzhi Wu, Xiangyu Wang, Jae-Myung Lee, Kwang-Hyo Jung. Incremental gradient-free method for nonsmooth distributed optimization. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1841-1857. doi: 10.3934/jimo.2017021

[11]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1835-1861. doi: 10.3934/jimo.2021046

[12]

Ya-Zheng Dang, Zhong-Hui Xue, Yan Gao, Jun-Xiang Li. Fast self-adaptive regularization iterative algorithm for solving split feasibility problem. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1555-1569. doi: 10.3934/jimo.2019017

[13]

Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075

[14]

Jie Shen, Jian Lv, Fang-Fang Guo, Ya-Li Gao, Rui Zhao. A new proximal chebychev center cutting plane algorithm for nonsmooth optimization and its convergence. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1143-1155. doi: 10.3934/jimo.2018003

[15]

Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185

[16]

Mohamed Aly Tawhid. Nonsmooth generalized complementarity as unconstrained optimization. Journal of Industrial and Management Optimization, 2010, 6 (2) : 411-423. doi: 10.3934/jimo.2010.6.411

[17]

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

[18]

Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015

[19]

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

[20]

Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1279-1296. doi: 10.3934/jimo.2014.10.1279

2020 Impact Factor: 1.639

Metrics

  • PDF downloads (39)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]