Combining line search and trust-region methods for ℓ1-minimization

References

• M. Ahookhosh, Optimal subgradient algorithms with application to large-scale linear inverse problems, Submitted, 2014. http://www.arxiv.org/abs/1402.7291.
   Google Scholar
• M. Ahookhosh, K. Amini, and M.R. Peyghami, A nonmonotone trust-region line search method for large-scale unconstrained optimization, Appl. Math. Model. 36 (2012), pp. 478–487. doi: 10.1016/j.apm.2011.07.021
   Web of Science ®Google Scholar
• M. Ahookhosh, H. Esmaeili, and M. Kimiaei, An effective trust-region-based approach for symmetric nonlinear systems, Int. J. Comput. Math. 90(3) (2013), pp. 671–690. doi: 10.1080/00207160.2012.736617
   Google Scholar
• J. Barzilai and J.M. Borwein, Two point step size gradient method, IMA J. Numer. Anal 8 (1988), pp. 141–148. doi: 10.1093/imanum/8.1.141
   Web of Science ®Google Scholar
• S. Becker, J. Bobin, and E. Candés, NESTA: A fast and accurate first-order method for sparse recovery, SIAM J. Imaging Sci. 4 (2011), pp. 1–39. doi: 10.1137/090756855
   Web of Science ®Google Scholar
• A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2(1) (2009), pp. 183–202. doi: 10.1137/080716542
   Web of Science ®Google Scholar
• J.M. Bioucas-Dias and M. Figueiredo, A new TwIST: Two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Trans. Image Process 16 (2007), pp. 2992–3004. doi: 10.1109/TIP.2007.909319
   PubMed Web of Science ®Google Scholar
• H. Boche, R. Calderbank, G. Kutyniok, and J. Vybíral, Compressed Sensing and its Applications, Applied and Numerical Harmonic Analysis, Springer, New York, 2015.
   Google Scholar
• A. Bouaricha and R.B. Schnabel, Tensor methods for large sparse systems of nonlinear equations, Math. Program. 82 (1998), pp. 377–400.
   Web of Science ®Google Scholar
• S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn. 3(1) (2011), pp. 1–122. doi: 10.1561/2200000016
   Google Scholar
• C.G. Broyden, The convergence of an algorithm for solving sparse nonlinear systems, Math. Comput. 25(114) (1971), pp. 285–294. doi: 10.1090/S0025-5718-1971-0297122-5
   Web of Science ®Google Scholar
• E. Candés, J. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math. 59 (2006), pp. 1207–1233. doi: 10.1002/cpa.20124
   Web of Science ®Google Scholar
• A. Chambolle, R.A. DeVore, N.Y. Lee, and B.J. Lucier, Nonlinear wavelet image processing: Variational problems, compression, and noise removal through wavelet shrinkage, IEEE Trans. Image Process 7 (1998), pp. 319–335. doi: 10.1109/83.661182
   PubMed Web of Science ®Google Scholar
• R.M. Chamberlain, M.J.D. Powell, C. Lemarechal, and H.C. Pedersen, The watchdog technique for forcing convergence in algorithm for constrained optimization, Math. Program. Stud 16 (1982), pp. 1–17. doi: 10.1007/BFb0120945
   Web of Science ®Google Scholar
• P.L. Combettes and J.C. Pesquet, Proximal splitting methods in signal processing, In: H.H. Bauschke, R. Burachik, P.L. Combettes, V. Elser, D.R. Luke, and H. Wolkowicz (eds.), Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer-Verlag, New York, 2010, pp. 185–212.
   Google Scholar
• I. Daubechies, M. Defrise, and C.D. Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pure Appl. Math 57 (2004), pp. 1413–1457. doi: 10.1002/cpa.20042
   Web of Science ®Google Scholar
• E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles, Math. Program. 91 (2002), pp. 201–213. doi: 10.1007/s101070100263
   Web of Science ®Google Scholar
• D.L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), pp. 1289–1306. doi: 10.1109/TIT.2006.871582
   Web of Science ®Google Scholar
• Y. Eldar and G. Kutyniok, Compressed Sensing: Theory and Applications, Cambridge University Press, New York, 2012.
   Google Scholar
• M.A.T. Figueiredo and R.D. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process 12 (2003), pp. 906–916. doi: 10.1109/TIP.2003.814255
   PubMed Web of Science ®Google Scholar
• 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. Topics Sig. Proc. 1(4) (2007), pp. 586–597.
   Google Scholar
• M. Friedlander and M. Saunders, A dual active-set quadratic programming method for finding sparse least-squares solutions, DRAFT Technical Report, Dept of Computer Science, University of British Columbia, July 30, 2012.
   Google Scholar
• E.M. Gertz, A quasi-Newton trust-region method, Math. Program, Ser. A 100 (2004), pp. 447–470.
   Web of Science ®Google Scholar
• L. Grippo, F. Lamparillo, and S. Lucidi, A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal 23 (1986), pp. 707–716. doi: 10.1137/0723046
   Web of Science ®Google Scholar
• E.T Hale, W. Yin, and Y. Zhang, A Fixed-Point Continuation Method for ℓ1-Regularized Minimization with Applications to Compressed Sensing, CAAM Technical Report TR07-07, July 7, 2007.
   Google Scholar
• E.T Hale, W. Yin, and Y. Zhang, Fixed-point continuation applied to compressed sensing: implementaion and numerical experiments, J. Comput. Math. 28(2) (2010), pp. 170–194.
   Web of Science ®Google Scholar
• J. Nocedal and S.J. Wright, Numerical Optimization, Springer, NewYork, 2006.
   Google Scholar
• N. Parikh and S. Boyd, Proximal algorithms, Found. Trends Optim. 1(3) (2013), pp. 123–231.
   Google Scholar
• P. Tseng and S. Yun, A Coordinate gradient descent method for nonsmooth separable minimization, Math. Program. 117 (2009), pp. 387–423. doi: 10.1007/s10107-007-0170-0
   Web of Science ®Google Scholar
• E. Van den Berg and M.P. Friedlander, Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput 31(2) (2008), pp. 890–912. doi: 10.1137/080714488
   Web of Science ®Google Scholar
• C. Vonesch and M. Unser, Fast iterative thresholding algorithm for wavelet-regularized deconvolution, In: Proceedings of the SPIE Optics and Photonics 2007 Conference on Mathematical Methods: Wavelet XII. Vol. 6701, San Diego, CA, 2007, pp. 1–5.
   Google Scholar
• F. Wang and M.K. Ng, A fast minimization method for blur and multiplicative noise removal, Int. J. Comput. Math. 90(1) (2013), pp. 48–61. doi: 10.1080/00207160.2012.688821
   Web of Science ®Google Scholar
• Z. Wen, W. Yin, D. Goldfarb, and Y. Zhang, A fast algorithm for sparse reconstruction based on sharinkage, subspased optimization, and conttinuation, SIAM J. Sci. Comput. 32(4) (2010), pp. 1832–1857. doi: 10.1137/090747695
   Web of Science ®Google Scholar
• Z. Wen, W. Yin, Y. Zhang, and D. Goldfarb, On the convergence of an active set method for ℓ1 minimization, Optim. Methods Softw. 27(6) (2012), pp. 1127–1146. doi: 10.1080/10556788.2011.591398
   Web of Science ®Google Scholar
• S.J. Wright, R.D. Nowak, and M.A.T. Figueiredo, Sparse reconstruction by separable approximation, IEEE Trans. Signal Process 57 (2009), pp. 2479–2493. doi: 10.1109/TSP.2009.2016892
   Web of Science ®Google Scholar
• Y. Xiao, S.Y. Wu, and L. Qi, Nonmonotone Brazilai-Borwein gradient algorithm for l1-regularized nonsmooth minimization in compressive sensing, J. Sci. Comput. 61 (2014), pp. 17–41. doi: 10.1007/s10915-013-9815-8
   Web of Science ®Google Scholar
• Y. Xiao, H. Zhu, and S.Y Wu, Primal and dual alternating direction algorithms for ℓ1-ℓ1-norm minimization problems in compressive sensing, Comput. Optim. Appl. 54 (2013), pp. 441–459. doi: 10.1007/s10589-012-9475-x
   Web of Science ®Google Scholar
• S. Yun and K.C. Toh, A coordinate gradient descent method for ℓ1-regularized convex minimization, Comput. Optim. Appl 48 (2011), pp. 273–307. doi: 10.1007/s10589-009-9251-8
   Web of Science ®Google Scholar