The nuclear norm is widely used to induce low-rank solutions for many optimization problems with matrix variables. Recently, it has been shown that the augmented Lagrangian method (ALM) and the alternating direction method (ADM) are very efficient for many convex programming problems arising from various applications, provided that the resulting subproblems are sufficiently simple to have closed-form solutions.<\/p>\n
In this paper, we are interested in the application of the ALM and the ADM for some nuclear norm involved minimization problems. When the resulting subproblems do not have closed-form solutions, we propose to linearize these subproblems such that closed-form solutions of these linearized subproblems can be easily derived.<\/p>\n
Global convergence results of these linearized ALM and ADM are established under standard assumptions. Finally, we verify the effectiveness and efficiency of these new methods by some numerical experiments.<\/p>","DOI":"10.1090\/s0025-5718-2012-02598-1","type":"journal-article","created":{"date-parts":[[2012,3,28]],"date-time":"2012-03-28T12:58:03Z","timestamp":1332939483000},"page":"301-329","source":"Crossref","is-referenced-by-count":317,"title":["Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization"],"prefix":"10.1090","volume":"82","author":[{"given":"Junfeng","family":"Yang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaoming","family":"Yuan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2012,3,28]]},"reference":[{"key":"1","unstructured":"J. Abernethy, F. Bach, T. Evgeniou and J.-P. Vert, A new approach to collaborative filtering: Operator estimation with spectral regularization, Journal of Machine Learning Research, 10(2009), pp. 803\u2013826."},{"key":"2","doi-asserted-by":"crossref","unstructured":"A. Argyriou, T. Evgeniou and M. Pontil, Convex multi-task feature learning, Machine Learning, 73(3)(2008), pp. 243\u2013272.","DOI":"10.1007\/s10994-007-5040-8"},{"key":"3","series-title":"CMS Books in Mathematics\/Ouvrages de Math\\'{e}matiques de la SMC","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-31256-9","volume-title":"Convex analysis and nonlinear optimization","volume":"3","author":"Borwein, Jonathan M.","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387295701","edition":"2"},{"issue":"4","key":"4","doi-asserted-by":"publisher","first-page":"1956","DOI":"10.1137\/080738970","article-title":"A singular value thresholding algorithm for matrix completion","volume":"20","author":"Cai, Jian-Feng","year":"2010","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"267","key":"5","doi-asserted-by":"publisher","first-page":"1515","DOI":"10.1090\/S0025-5718-08-02189-3","article-title":"Linearized Bregman iterations for compressed sensing","volume":"78","author":"Cai, Jian-Feng","year":"2009","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"268","key":"6","doi-asserted-by":"publisher","first-page":"2127","DOI":"10.1090\/S0025-5718-09-02242-X","article-title":"Convergence of the linearized Bregman iteration for \u2113\u2081-norm minimization","volume":"78","author":"Cai, Jian-Feng","year":"2009","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"7","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1137\/090753504","article-title":"Split Bregman methods and frame based image restoration","volume":"8","author":"Cai, Jian-Feng","year":"2009","journal-title":"Multiscale Model. Simul.","ISSN":"https:\/\/id.crossref.org\/issn\/1540-3459","issn-type":"print"},{"issue":"6","key":"8","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","article-title":"Exact matrix completion via convex optimization","volume":"9","author":"Cand\u00e8s, Emmanuel J.","year":"2009","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"issue":"5","key":"9","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1109\/TIT.2010.2044061","article-title":"The power of convex relaxation: near-optimal matrix completion","volume":"56","author":"Cand\u00e8s, Emmanuel J.","year":"2010","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"10","unstructured":"C. H. Chen, B. S. He and X. M. Yuan, Matrix completion via alternating direction methods, IMA Journal of Numerical Analysis, to appear."},{"issue":"4","key":"11","doi-asserted-by":"publisher","first-page":"1168","DOI":"10.1137\/050626090","article-title":"Signal recovery by proximal forward-backward splitting","volume":"4","author":"Combettes, Patrick L.","year":"2005","journal-title":"Multiscale Model. Simul.","ISSN":"https:\/\/id.crossref.org\/issn\/1540-3459","issn-type":"print"},{"key":"12","isbn-type":"print","first-page":"115","article-title":"Some reformulations and applications of the alternating direction method of multipliers","author":"Eckstein, Jonathan","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0792327985"},{"key":"13","unstructured":"E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split Bregman, preprint, available at \\url{http:\/\/www.math.ucla.edu\/applied\/cam\/}, 2009."},{"key":"14","doi-asserted-by":"crossref","unstructured":"M. Fazel, H. Hindi and S. Boyd, A rank minimization heuristic with application to minimum order system approximation, Proceedings American Control Conference, 6(2001), pp. 4734\u20134739.","DOI":"10.1109\/ACC.2001.945730"},{"issue":"1","key":"15","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF00247655","article-title":"Application of the alternating direction method of multipliers to separable convex programming problems","volume":"1","author":"Fukushima, Masao","year":"1992","journal-title":"Comput. Optim. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0926-6003","issn-type":"print"},{"key":"16","doi-asserted-by":"crossref","unstructured":"D. Gabay, Application of the method of multipliers to varuational inequalities, In: Fortin, M., Glowinski, R., eds., Augmented Lagrangian methods: Application to the numerical solution of Boundary-Value Problem, North-Holland, Amsterdam, The Netherlands, pp. 299\u2013331, 1983.","DOI":"10.1016\/S0168-2024(08)70034-1"},{"key":"17","doi-asserted-by":"crossref","unstructured":"D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Computational Mathematics with Applications, 2(1976), pp. 17\u201340.","DOI":"10.1016\/0898-1221(76)90003-1"},{"key":"18","series-title":"SIAM Studies in Applied Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970838","volume-title":"Augmented Lagrangian and operator-splitting methods in nonlinear mechanics","volume":"9","author":"Glowinski, Roland","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0898712300"},{"issue":"2","key":"19","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/080725891","article-title":"The split Bregman method for \ud835\udc3f1-regularized problems","volume":"2","author":"Goldstein, Tom","year":"2009","journal-title":"SIAM J. Imaging Sci."},{"issue":"3","key":"20","doi-asserted-by":"publisher","first-page":"1107","DOI":"10.1137\/070698920","article-title":"Fixed-point continuation for \ud835\udc59\u2081-minimization: methodology and convergence","volume":"19","author":"Hale, Elaine T.","year":"2008","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"1","key":"21","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s101070100280","article-title":"A new inexact alternating directions method for monotone variational inequalities","volume":"92","author":"He, Bingsheng","year":"2002","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"issue":"1","key":"22","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1137\/090761549","article-title":"Solving large-scale least squares semidefinite programming by alternating direction methods","volume":"32","author":"He, Bingsheng","year":"2011","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"3-5","key":"23","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0167-6377(98)00044-3","article-title":"Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities","volume":"23","author":"He, Bingsheng","year":"1998","journal-title":"Oper. Res. Lett.","ISSN":"https:\/\/id.crossref.org\/issn\/0167-6377","issn-type":"print"},{"issue":"2","key":"24","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1023\/A:1004603514434","article-title":"Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities","volume":"106","author":"He, B. S.","year":"2000","journal-title":"J. Optim. Theory Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-3239","issn-type":"print"},{"key":"25","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF00927673","article-title":"Multiplier and gradient methods","volume":"4","author":"Hestenes, Magnus R.","year":"1969","journal-title":"J. Optim. Theory Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-3239","issn-type":"print"},{"key":"26","doi-asserted-by":"crossref","unstructured":"S. Ji and J. Ye, An accelerated gradient method for trace norm minimization, The Twenty-Sixth International Conference on Machine Learning, 2009.","DOI":"10.1145\/1553374.1553434"},{"issue":"1","key":"27","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0025-5610(97)00103-2","article-title":"A variable-penalty alternating directions method for convex optimization","volume":"83","author":"Kontogiorgis, Spyridon","year":"1998","journal-title":"Math. Programming","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"key":"28","unstructured":"R. M. Larsen, PROPACK-Software for large and sparse SVD calculations, Available at: \\url{http:\/\/sun.stanfor.edu\/srmunk\/PROPACK\/}, 2005."},{"key":"29","unstructured":"Z.-C. Lin, M.-M. Chen, L.-Q. Wu and Y. Ma, The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices, manuscript, 2009."},{"key":"30","unstructured":"J. Liu, S. Ji and J. Ye, SLEP: A Sparse Learning Package, Version 2.0, Available at: \\url{http:\/\/www.public.asu.edu\/ jye02\/Software\/SLEP}, 2010."},{"key":"31","unstructured":"Y. J. Liu, D. F. Sun and K. C. Toh, An implementable proximal point algorithmic framework for nuclear norm minimization, Mathematical Programming, to appear."},{"issue":"1-2","key":"32","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s10107-009-0306-5","article-title":"Fixed point and Bregman iterative methods for matrix rank minimization","volume":"128","author":"Ma, Shiqian","year":"2011","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"issue":"3","key":"33","first-page":"543","article-title":"A method for solving the convex programming problem with convergence rate \ud835\udc42(1\/\ud835\udc58\u00b2)","volume":"269","author":"Nesterov, Yu. E.","year":"1983","journal-title":"Dokl. Akad. Nauk SSSR","ISSN":"https:\/\/id.crossref.org\/issn\/0002-3264","issn-type":"print"},{"issue":"1","key":"34","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","article-title":"Smooth minimization of non-smooth functions","volume":"103","author":"Nesterov, Yu.","year":"2005","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"issue":"5","key":"35","doi-asserted-by":"publisher","first-page":"2710","DOI":"10.1137\/090774823","article-title":"Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods","volume":"32","author":"Ng, Michael K.","year":"2010","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"2","key":"36","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s11222-008-9111-x","article-title":"Joint covariate selection and joint subspace selection for multiple classification problems","volume":"20","author":"Obozinski, Guillaume","year":"2010","journal-title":"Stat. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0960-3174","issn-type":"print"},{"issue":"2","key":"37","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1137\/040605412","article-title":"An iterative regularization method for total variation-based image restoration","volume":"4","author":"Osher, Stanley","year":"2005","journal-title":"Multiscale Model. Simul.","ISSN":"https:\/\/id.crossref.org\/issn\/1540-3459","issn-type":"print"},{"issue":"6","key":"38","doi-asserted-by":"publisher","first-page":"3465","DOI":"10.1137\/090763184","article-title":"Trace norm regularization: reformulations, algorithms, and multi-task learning","volume":"20","author":"Pong, Ting Kei","year":"2010","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"key":"39","first-page":"283","article-title":"A method for nonlinear constraints in minimization problems","author":"Powell, M. J. D.","year":"1969"},{"issue":"3","key":"40","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/070697835","article-title":"Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization","volume":"52","author":"Recht, Benjamin","year":"2010","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"key":"41","series-title":"Princeton Mathematical Series, No. 28","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","volume-title":"Convex analysis","author":"Rockafellar, R. Tyrrell","year":"1970"},{"issue":"2","key":"42","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1287\/moor.1.2.97","article-title":"Augmented Lagrangians and applications of the proximal point algorithm in convex programming","volume":"1","author":"Rockafellar, R. T.","year":"1976","journal-title":"Math. Oper. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/0364-765X","issn-type":"print"},{"key":"43","doi-asserted-by":"crossref","unstructured":"S. Setzer, G. Steidl and T. Teuber, Deblurring Poissonian images by split Bregman techniques, Journal of Visual Communication and Image Representation, 21 (2010), pp. 193-199.","DOI":"10.1016\/j.jvcir.2009.10.006"},{"key":"44","unstructured":"N. Srebro, J. D. M. Rennie and T. S. Jaakkola, Maximum-margin matrix factorization, Advances in Neural Information Processing System, (2005), pp. 1329\u20131336."},{"issue":"1-4","key":"45","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1080\/10556789908805766","article-title":"Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones","volume":"11\/12","author":"Sturm, Jos F.","year":"1999","journal-title":"Optim. Methods Softw.","ISSN":"https:\/\/id.crossref.org\/issn\/1055-6788","issn-type":"print"},{"key":"46","series-title":"Springer Optimization and Its Applications","isbn-type":"print","volume-title":"Optimization theory and methods","volume":"1","author":"Sun, Wenyu","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387249759"},{"issue":"3","key":"47","doi-asserted-by":"publisher","first-page":"1210","DOI":"10.1016\/j.ejor.2010.07.020","article-title":"A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs","volume":"207","author":"Sun, Jie","year":"2010","journal-title":"European J. Oper. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-2217","issn-type":"print"},{"issue":"1","key":"48","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/100781894","article-title":"Recovering low-rank and sparse components of matrices from incomplete and noisy observations","volume":"21","author":"Tao, Min","year":"2011","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"3","key":"49","first-page":"615","article-title":"An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems","volume":"6","author":"Toh, Kim-Chuan","year":"2010","journal-title":"Pac. J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1348-9151","issn-type":"print"},{"issue":"4","key":"50","doi-asserted-by":"publisher","first-page":"951","DOI":"10.1137\/S1052623495279797","article-title":"Alternating projection-proximal methods for convex programming and variational inequalities","volume":"7","author":"Tseng, Paul","year":"1997","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"2","key":"51","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10107-002-0347-5","article-title":"Solving semidefinite-quadratic-linear programs using SDPT3","volume":"95","author":"T\u00fct\u00fcnc\u00fc, R. H.","year":"2003","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"key":"52","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0024-3795(92)90407-2","article-title":"Characterization of the subdifferential of some matrix norms","volume":"170","author":"Watson, G. A.","year":"1992","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"3-4","key":"53","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s12532-010-0017-1","article-title":"Alternating direction augmented Lagrangian methods for semidefinite programming","volume":"2","author":"Wen, Zaiwen","year":"2010","journal-title":"Math. Program. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1867-2949","issn-type":"print"},{"key":"54","unstructured":"Z. W. Wen, W. Yin and Y. Zhang, Solving a low-rank factorization model for matrix completion by a non-linear successive over-relaxation algorithm, TR10-07, CAAM, Rice University, 2010."},{"issue":"1","key":"55","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1137\/090777761","article-title":"Alternating direction algorithms for \u2113\u2081-problems in compressive sensing","volume":"33","author":"Yang, Junfeng","year":"2011","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"4","key":"56","doi-asserted-by":"publisher","first-page":"856","DOI":"10.1137\/090760350","article-title":"Analysis and generalizations of the linearized Bregman model","volume":"3","author":"Yin, Wotao","year":"2010","journal-title":"SIAM J. Imaging Sci."},{"issue":"1","key":"57","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/070703983","article-title":"Bregman iterative algorithms for \ud835\udc59\u2081-minimization with applications to compressed sensing","volume":"1","author":"Yin, Wotao","year":"2008","journal-title":"SIAM J. Imaging Sci."},{"issue":"3","key":"58","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1137\/090746379","article-title":"Bregmanized nonlocal regularization for deconvolution and sparse reconstruction","volume":"3","author":"Zhang, Xiaoqun","year":"2010","journal-title":"SIAM J. Imaging Sci."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2013-82-281\/S0025-5718-2012-02598-1\/S0025-5718-2012-02598-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2013-82-281\/S0025-5718-2012-02598-1\/S0025-5718-2012-02598-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T17:25:16Z","timestamp":1776792316000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2013-82-281\/S0025-5718-2012-02598-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,28]]},"references-count":58,"journal-issue":{"issue":"281","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["S0025-5718-2012-02598-1"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2012-02598-1","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2012,3,28]]}}}