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

Summary: We present a proximal quasi-Newton method in which the approximation of the Hessian has the special format of “identity minus rank one” (IMRO) in each iteration. The proposed structure enables us to effectively recover the proximal point. The algorithm is applied to \(\ell_1\)-regularized least squares problems arising in many applications including sparse recovery in compressive sensing, machine learning, and statistics. Our numerical experiment suggests that the proposed technique competes favorably with other state-of-the-art solvers for this class of problems. We also provide a complexity analysis for variants of IMRO, showing that it matches known best bounds.

### 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 |

### Keywords:

proximal methods; quasi-Newton methods; sparse recovery; basis pursuit denoising problem; \(\ell_1\)-regularized least squares problem; convex optimization; minimization of composite functions### Software:

SPGL1; UNLocBoX; ParNes; FPC_AS; NESTA; NNLS; LBFGS-B; TwIST; RecPF; l1_ls; IMRO; SpaRSA; FPC; PNOPT; L1TestPack; TFOCS
PDFBibTeX
XMLCite

\textit{S. Karimi} and \textit{S. Vavasis}, SIAM J. Optim. 27, No. 2, 583--615 (2017; Zbl 1365.90202)

### References:

[1] | R. Baraniuk, {\it Compressive sensing}, IEEE Signal Process. Mag., 24 (2007), pp. 118-121. |

[2] | J. Barzilai and J. Borwein, {\it Two point step size gradient method}, IMA J. Numer. Anal., 8 (1988), pp. 141-148. · Zbl 0638.65055 |

[3] | A. Beck and M. Teboulle, {\it 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, {\it Z}ero SR1 Quasi-Newton Method, (2014). |

[5] | S. Becker, J. Bobin, and E. Candès, {\it 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. Candès, and M. Grant, {\it Software: Templates for Convex Cone Problems with Applications to Sparse Signal Recovery (TFOCS)}, , (2011). · Zbl 1257.90042 |

[7] | S. Becker, E. J. Candès, and M. Grant, {\it Templates for convex cone problems with applications to sparse signal recovery}, Math. Program. Comput., 3 (2011), 165. · Zbl 1257.90042 |

[8] | S. Becker and M. J. Fadili, {\it A Quasi-Newton Proximal Splitting Method}, preprint, arXiv:1206.1156v1, 2012, . |

[9] | E. van den Berg and M. P. Friedlander, {\it SPGL1: A Solver for Large-Scale Sparse Reconstruction}, . |

[10] | E. van den Berg and M. P. Friedlander, {\it 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, {\it 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 Ö. Y\ilmaz, {\it 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, {\it TwIST: Two-Step Iterative Shrinkage/Thresholding Algorithm for Linear Inverse Problems}, . |

[14] | J. M. Bioucas-Dias and M. A. T. Figueiredo, {\it 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. Martínez, and M. Raydan, {\it 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. Martínez, and M. Raydan, {\it 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, {\it 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, {\it A limited memory algorithm for bound constrained optimization}, SIAM J. Sci. Comput., 16 (1995), pp. 1190-1208. · Zbl 0836.65080 |

[19] | E. Candès, {\it Compressive sampling}, in International Congress of Mathematics, European Mathematical Society, Vol. 3, Zurich, 2006, pp. 1433-1452. · Zbl 1130.94013 |

[20] | E. Candès, J. Romberg, and T. Tao, {\it 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. Candès and T. Tao, {\it Near optimal signal recovery from random projections: Universal encoding strategies}, IEEE Trans. Inform. Theory, 52 (2006), pp. 5406-5425. · Zbl 1309.94033 |

[22] | E. Candès and M. Wakin, {\it An introduction to compressive sampling}, IEEE Signal Process. Mag., 25 (2008), pp. 21-30. |

[23] | P. L. Combettes and V. R. Wajs, {\it 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, {\it 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, {\it 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, {\it Compressed sensing}, IEEE Trans. Inform. Theory, 52 (2006), pp. 1289-1306. · Zbl 1288.94016 |

[27] | M. A. T. Figueiredo and R. D. Nowak, {\it 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, {\it GPSR: Gradient Projection for Sparse Reconstruction}, . |

[29] | M. A. T. Figueiredo, R. D. Nowak, and S. J. Wright, {\it SpaRSA: Sparse Reconstruction by Separable Approximation}, . · Zbl 1391.94442 |

[30] | M. A. T. Figueiredo, R. D. Nowak, and S. J. Wright, {\it 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, {\it 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, {\it 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, {\it 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, {\it Fixed Point Continuation (FPC)}, . |

[35] | E. T. Hale, W. Yin, and Y. Zhang, {\it 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, {\it Fixed-point continuation for \(l_1\)-minimization: Methodology and convergence}, SIAM J. Optim., 19 (2008), pp. 1107-1130. · Zbl 1180.65076 |

[37] | S. Karimi, {\it 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, {\it 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, {\it 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, {\it \(l_1_l\) s: Simple Matlab Solver for \(l_1\)-Regularized Least Squares Problems}, . |

[41] | J. D. Lee, Y. Sun, and M. A. Saunders, {\it PNOPT}, . |

[42] | J. D. Lee, Y. Sun, and M. A. Saunders, {\it 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, {\it Nonsmooth optimization via quasi-Newton methods}, Math. Program., 141 (2013), pp. 135-163. · Zbl 1280.90118 |

[44] | D. A. Lorenz, {\it L1TestPack: A software to generate test instances for \(l_1\) minimization problems}, 2011, . |

[45] | Y. E. Nesterov, {\it 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, {\it Introductory Lectures on Convex Optimization: A Basic Course}. Springer, New York, 2004. · Zbl 1086.90045 |

[47] | Y. E. Nesterov, {\it Smooth minimization of nonsmooth functions}, Math. Program., 103 (2005), pp. 127-152. · Zbl 1079.90102 |

[48] | J. Nocedal and S. J. Wright, {\it Numerical Optimization}, Springer, Berlin, 2006. · Zbl 1104.65059 |

[49] | M. Schmidt, E. van den Berg, M. Friedlander, and K. Murphy, {\it 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, {\it FPC_AS}: A MATLAB Solver for \(l_1\)-regularization problems, . |

[51] | Z. Wen, W. Yin, D. Goldfarb, and Y. Zhang, {\it 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, {\it 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, {\it 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, {\it Alternating Direction Algorithms for \(l_1\)-Problems in Compressive Sensing}, preprint, arXiv:0912.1185, 2009. |

[55] | J. Yang, Y. Zhang, and W. Yin, {\it 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, {\it 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. Günter, and N. N. Schraudolph, {\it 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.