Generalized Conjugate Gradient Methods for ℓ₁ Regularized Convex Quadratic Programming with Finite Convergence

References

• Afonso MV, Bioucas-Dias JM, Figueiredo MAT (2010) Fast image recovery using variable splitting and constrained optimization. IEEE T. Signal Proces. 19(9):2345–2356.Google Scholar
• Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1):183–202.Crossref, Google Scholar
• Becker SR, Candès EJ, Grant MC (2011) Templates for convex cone problems with applications to sparse signal recovery. Math. Prog. Comput. 3(3):165–218.Crossref, Google Scholar
• Bioucas-Dias JM, Figueiredo MAT (2007) A new TwIST: Two-step iterative shrinkage/thresholding algorithms for image restoration. IEEE T. Signal Proces. 16(12):2992–3004.Google Scholar
• Bruckstein AM, Donoho DL, Elad M (2009) From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51(1):34–81.Crossref, Google Scholar
• Byrd RH, Nocedal J, Solntsev S (2015) An algorithm for quadratic ℓ1-regularized optimization with a flexible active-set strategy. Optim. Method Softw. 30(6):1213–1237.Crossref, Google Scholar
• Candès E, Romberg J (2005) ℓ1-magic: Recovery of sparse signals via convex programming. User’s Guide, Applied and Computational Mathematics (California Institute of Technology, Pasadena, CA).Google Scholar
• Chen S, Donoho D, Saunders M (1998) Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1):33–61.Crossref, Google Scholar
• Deng W, Yin W, Zhang Y (2011) Group sparse optimization by alternating direction method. CAAM Technical Report TR11-06, Rice University, Houston, TX.Google Scholar
• Donoho DL (1995) De-noising by soft-thresholding. IEEE Trans. Inform. Theory 41(3):613–627.Crossref, Google Scholar
• Dostal Z (1997) Box constrained quadratic programming with proportioning and projections. SIAM J. Optim. 7(3):871–887.Crossref, Google Scholar
• Dostal Z, Schöberl J (2005) Minimizing quadratic functions subject to bound constrained with the rate of convergence and finite termination. Comp. Optim. Appl. 30(1):23–43.Crossref, Google Scholar
• Fountoulakis K, Gondzio J (2016) A second-order method for strongly-convex ℓ1-regularization problems. Math. Prog. 156(1):189–219.Crossref, Google Scholar
• Goldstein T, Osher S (2009) The split Bregman method for ℓ1-regularized problems. SIAM J. Imaging Sci. 2(2):323–343.Crossref, Google Scholar
• Hale ET, Yin W, Zhang Y (2010) Fixed-point continuation applied to compressed sensing: Implementation and numerical experiments. J. Comput. Math. 28(2):170–194.Google Scholar
• Hastie T, Tibshirani R, Friedman JH (2001) The Elements in Statistical Learning: Data Mining, Inference, and Prediction (Springer, New York).Crossref, Google Scholar
• Hayami K (2001) On the behavior of the conjugate residual method for singular systems. NII Technical Report, National Institute of Informatics, Tokyo.Google Scholar
• Kaasschieter EF (1988) Preconditioned conjugate gradients for solving singular systems. J. Comput. Appl. Math. 24(1–2):265–275.Crossref, Google Scholar
• Kammerer WJ, Nashed MZ (1972) On the convergence of the conjugate gradient method for singular linear operator equations. SIAM J. Numer. Anal. 9(1):165–181.Crossref, Google Scholar
• Kim S-J, Koh K, Lustig M, Boyd S, Gorinevsky D (2007) An interior-point method for large-scale ℓ1-regularized least squares. IEEE T. Signal Proces. 1(4):606–617.Crossref, Google Scholar
• Li W (1995) Error bounds for piecewise convex quadratic programs and applications. SIAM J. Control Optim. 33(5):1510–1529.Crossref, Google Scholar
• Milzarek A, Ulbrich M (2014) A semismooth Newton method with multidimensional filter globalization for l1-optimization. SIAM J. Optim. 24(1):298–333.Crossref, Google Scholar
• Nesterov Y (2013) Gradient methods for minimizing composite functions. Math. Program. 140(1):125–161.Crossref, Google Scholar
• Nocedal J, Wright SJ (2006) Numerical Optimization, 2nd ed. (Springer, New York).Google Scholar
• O’Leary DP (1980) A generalized conjugate gradient algorithm for solving a class of quadratic programming problems. Linear Alg. Appl. 34:371–399.Crossref, Google Scholar
• Robinson SM (1981) Some continuity properties of polyhedral multifunctions. Math. Program. Stud. 14:206–214.Crossref, Google Scholar
• Schmidt M (2010) Graphical Model Structure Learning with ℓ1-Regularization. PhD thesis, University of British Columbia, Vancouver.Google Scholar
• Sra S, Nowozin S, Wright SJ (2011) Optimization for Machine Learning (MIT Press, Cambridge, MA).Crossref, Google Scholar
• Steihaug T (1983) The conjugate gradient method and trust regions in large scale optimization. SIAM J. Numer. Anal. 20(3):626–637.Crossref, Google Scholar
• Toint PL (1981) Towards an efficient sparsity exploiting Newton method for minimization. Duff IS, ed., Sparse Matrices and Their Uses (Academic Press, London), 57–88.Google Scholar
• Wright SJ, Nowak R, Figueiredo MAT (2009) Sparse reconstruction by separable approximation. IEEE T. Signal Proces. 57(7):2479–2493.Crossref, Google Scholar
• Xiao L, Zhang T (2013) A proximal-gradient homotopy method for the sparse least-squares problem. SIAM J. Optim. 23(2):1062–1091.Crossref, Google Scholar
• Yang J, Zhang Y (2010) Alternating direction algorithm for ℓ1-problems in compressive sensing. SIAM J. Sci. Comput. 33(1):250–278.Crossref, Google Scholar
• Yun S, Toh K-C (2011) A coordinate gradient descent method for l1-regularized convex minimization. Comput. Optim. Appl. 48(2):273–307.Crossref, Google Scholar