# zbMATH — the first resource for mathematics

IMRO: A proximal quasi-Newton method for solving $$\ell_1$$-regularized least squares problems. (English) Zbl 1365.90202

##### MSC:
 90C25 Convex programming 90C30 Nonlinear programming 90C53 Methods of quasi-Newton type 90C90 Applications of mathematical programming 65K05 Numerical mathematical programming methods 49M37 Numerical methods based on nonlinear programming 49M15 Newton-type methods
##### Software:
L1TestPack; LBFGS-B; PNOPT; UNLocBoX; NNLS; NESTA; TwIST; SPGL1; ParNes; l1_ls; RecPF; FPC_AS; IMRO; SpaRSA; TFOCS; FPC
Full Text:
##### References:
 [1] R. Baraniuk, Compressive sensing, IEEE Signal Process. Mag., 24 (2007), pp. 118–121. [2] J. Barzilai and J. Borwein, Two point step size gradient method, IMA J. Numer. Anal., 8 (1988), pp. 141–148. · Zbl 0638.65055 [3] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183–202. · Zbl 1175.94009 [4] S. Becker, Zero SR1 Quasi-Newton Method, (2014). [5] S. Becker, J. Bobin, and E. Candès, NESTA: A fast and accurate first-order method for sparse recovery, SIAM J. Imaging Sci., 4 (2011), pp. 1–39. · Zbl 1209.90265 [6] S. Becker, E. J. Candès, and M. Grant, Software: Templates for Convex Cone Problems with Applications to Sparse Signal Recovery (TFOCS), , (2011). [7] S. Becker, E. J. Candès, and M. Grant, Templates for convex cone problems with applications to sparse signal recovery, Math. Program. Comput., 3 (2011), 165. [8] S. Becker and M. J. Fadili, A Quasi-Newton Proximal Splitting Method, preprint, arXiv:1206.1156v1, 2012, . [9] E. van den Berg and M. P. Friedlander, SPGL1: A Solver for Large-Scale Sparse Reconstruction, . [10] E. van den Berg and M. P. Friedlander, In Pursuit of a Root, Technical report TR-2007-19, Department of Computer Science, University of British Columbia, Vancouver, Canada, 2007, . [11] E. van den Berg and M. P. Friedlander, Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31 (2009), pp. 890–912. · Zbl 1193.49033 [12] E. van den Berg, M. P. Friedlander, G. Hennenfent, F. Herrmann, R. Saab, and Ö. Y\ilmaz, Sparco: A Testing Framework for Sparse Reconstruction, Technical report TR-2007-20, Department of Computer Science, University of British Columbia, Vancouver, Canada, 2007, . [13] J. M. Bioucas-Dias and M. A. T. Figueiredo, TwIST: Two-Step Iterative Shrinkage/Thresholding Algorithm for Linear Inverse Problems, . [14] 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), pp. 2992–3004. [15] E. G. Birgin, J. M. Martínez, and M. Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., 10 (2000), pp. 1196–1211. · Zbl 1047.90077 [16] E. G. Birgin, J. M. Martínez, and M. Raydan, Inexact spectral projected gradient methods on convex sets, IMA J. Numer. Anal., 23 (2003), pp. 539–559. · Zbl 1047.65042 [17] K. Bredies and D. A. Lorenz, Linear convergence of iterative soft-thresholding, J. Fourier Anal. Appl., 14 (2008), pp. 813–837. · Zbl 1175.65061 [18] R. H. Byrd, P. Lu, J. Nocedal, and C. Zhu, A limited memory algorithm for bound constrained optimization, SIAM J. Sci. Comput., 16 (1995), pp. 1190–1208. · Zbl 0836.65080 [19] E. Candès, Compressive sampling, in International Congress of Mathematics, European Mathematical Society, Vol. 3, Zurich, 2006, pp. 1433–1452. [20] E. Candès, J. Romberg, and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52 (2006), pp. 489–509. · Zbl 1231.94017 [21] E. Candès and T. Tao, Near optimal signal recovery from random projections: Universal encoding strategies, IEEE Trans. Inform. Theory, 52 (2006), pp. 5406–5425. · Zbl 1309.94033 [22] E. Candès and M. Wakin, An introduction to compressive sampling, IEEE Signal Process. Mag., 25 (2008), pp. 21–30. [23] P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4 (2005), pp. 1168–1200. · Zbl 1179.94031 [24] P. L. Combettes and J.-C. Pesquet, Proximal thresholding algorithm for minimization over orthonormal bases, SIAM J. Optim., 18 (2008), pp. 1351–1376. · Zbl 1167.90011 [25] P. L. Combettes and J. C. Pesquet, Proximal splitting methods in signal processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer, New York, 2011, pp. 185–212. · Zbl 1242.90160 [26] D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), pp. 1289–1306. · Zbl 1288.94016 [27] 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. · Zbl 1279.94015 [28] M. A. T. Figueiredo, R. D. Nowak, and S. J. Wright, GPSR: Gradient Projection for Sparse Reconstruction, . [29] M. A. T. Figueiredo, R. D. Nowak, and S. J. Wright, SpaRSA: Sparse Reconstruction by Separable Approximation, . · Zbl 1391.94442 [30] 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), pp. 586–597. [31] M. Fukushima and H. Mine, A generalized proximal point algorithm for certain non-convex minimization problems, Internat. J. Systems Sci., 12 (1981), pp. 989–1000. · Zbl 0467.65028 [32] D. Goldfarb, S. Ma, and K. Scheinberg, Fast alternating linearization methods for minimizing the sum of two convex functions, Math. Program., 141 (2013), pp. 349–382. · Zbl 1280.65051 [33] M. Gu, L. Lim, and C. Wu, ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals, Numer. Algorithms, 64 (2013), pp. 321–347. · Zbl 1284.65055 [34] E. T. Hale, W. Yin, and Y. Zhang, Fixed Point Continuation (FPC), . [35] E. T. Hale, W. Yin, and Y. Zhang, A Fixed-Point Continuation Method for $$l_1$$-Regularized Minimization with Applications to Compressed Sensing, Technical report TR07-07, Rice University, Houston, TX, 2007. [36] E. T. Hale, W. Yin, and Y. Zhang, Fixed-point continuation for $$l_1$$-minimization: Methodology and convergence, SIAM J. Optim., 19 (2008), pp. 1107–1130. · Zbl 1180.65076 [37] S. Karimi, On the Relationship between Conjugate Gradient and Optimal Methods for Convex Optimization, Ph.D. thesis, University of Waterloo, Waterloo, Canada, 2013. [38] D. Kim, S. Sra, and I. S. Dhillon, Tackling box-constrained optimization via a new projected quasi-Newton approach, SIAM J. Sci. Comput., 32 (2010), pp. 3548–3563. · Zbl 1220.93085 [39] S. 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), pp. 606–617. [40] K. Koh, S. Kim, S. Boyd, and Y. Lin, $$l_1$$_ls: Simple Matlab Solver for $$l_1$$-Regularized Least Squares Problems, . [41] J. D. Lee, Y. Sun, and M. A. Saunders, PNOPT, . [42] J. D. Lee, Y. Sun, and M. A. Saunders, Proximal Newton-type methods for minimizing composite functions, SIAM J. Optim., 24 (2014), pp. 1420–1443. · Zbl 1306.65213 [43] A. S. Lewis and M. L. Overton, Nonsmooth optimization via quasi-Newton methods, Math. Program., 141 (2013), pp. 135–163. · Zbl 1280.90118 [44] D. A. Lorenz, L1TestPack: A software to generate test instances for $$l_1$$ minimization problems, 2011, . [45] Y. E. Nesterov, A method of solving a convex programming problem with convergence rate $$o(\frac{1}{k^2})$$, Sov. Math. Dokl., 27 (1983), pp. 372–376. · Zbl 0535.90071 [46] Y. E. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course. Springer, New York, 2004. · Zbl 1086.90045 [47] Y. E. Nesterov, Smooth minimization of nonsmooth functions, Math. Program., 103 (2005), pp. 127–152. · Zbl 1079.90102 [48] J. Nocedal and S. J. Wright, Numerical Optimization, Springer, Berlin, 2006. · Zbl 1104.65059 [49] M. Schmidt, E. van den Berg, M. Friedlander, and K. Murphy, Optimizing costly functions with simple constraints: A limited-memory projected quasi-Newton algorithm, in J. Mach. Learn. Res. Workshop Conf., 5 (2009), pp. 456–463. [50] Z. Wen, W. Yin, D. Goldfarb, and Y. Zhang, FPC_AS: A MATLAB Solver for $$l_1$$-regularization problems, . [51] Z. Wen, W. 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), pp. 1832–1857. · Zbl 1215.49039 [52] 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. · Zbl 1391.94442 [53] T. Yamamoto, M. Yamagishi, and I. Yamada, Adaptive proximal forward-backward splitting for sparse system identification under impulsive noise, in 20th European Signal Processing Conference (EUSIPCO), IEEE, Piscataway, NJ, 2012, pp. 2620–2624. [54] J. Yang and Y. Zhang, Alternating Direction Algorithms for $$l_1$$-Problems in Compressive Sensing, preprint, arXiv:0912.1185, 2009. [55] J. Yang, Y. Zhang, and W. Yin, A fast alternating direction method for TVL1-L2 signal reconstruction from partial Fourier data, IEEE J. Sel. Top. Signal Process., 4 (2010), pp. 228–297. [56] 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), pp. 143–168. · Zbl 1203.90153 [57] J. Yu, S. V. N. Vishwanathan, S. Günter, and N. N. Schraudolph, A quasi-Newton approach to nonsmooth convex optimization problems in machine learning, J. Mach. Learn. Res., 11 (2010), pp. 1145–1200. · Zbl 1242.90296
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.