Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization

Authors:
Junfeng Yang and Xiaoming Yuan

Journal:
Math. Comp. **82** (2013), 301-329

MSC (2010):
Primary 90C25, 90C06, 65K05

DOI:
https://doi.org/10.1090/S0025-5718-2012-02598-1

Published electronically:
March 28, 2012

MathSciNet review:
2983026

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

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.

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.

**1.**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-826.**2.**A. ARGYRIOU, T. EVGENIOU AND M. PONTIL,*Convex multi-task feature learning*, Machine Learning, 73(3)(2008), pp. 243-272.**3.**J. M. BORWEIN, AND A. S. LEWIS,*Convex analysis and nonlinear optimization*, Springer-Verlag, 2003. MR**2184742 (2006f:49001)****4.**J. F. CAI, E. J. CANDÉS AND Z. W. SHEN,*A singular value thresholding algorithm for matrix completion*, SIAM Journal on Optimization, 20(4) (2010), pp. 1956-1982. MR**2600248 (2011c:90065)****5.**J. F. CAI, S. OSHER AND Z. SHEN,*Linearized Bregman iterations for compressed sensing*, Mathematics of Computation, 78(267)(2009), pp. 1515-1536. MR**2501061 (2010e:65086)****6.**J. F. CAI, S. OSHER AND Z. SHEN,*Convergence of the Linearized Bregman Iteration for -Norm Minimization*, Mathematics of Computation, 78(268) (2009), pp. 2127-2136. MR**2521281 (2010k:65111)****7.**J. F. CAI, S. OSHER AND Z. SHEN,*Split Bregman Methods and Frame Based Image Restoration*, Multiscale Model. Simul., 8(2)(2009), pp. 337-369. MR**2581025 (2011a:94016)****8.**E. J. CANDÈS AND B. RECHT,*Exact matrix completion via convex optimization*, Foundations of Computational Mathematics, 9(2009), pp. 717-772. MR**2565240 (2011c:90066)****9.**E. J. CANDÈS AND T. TAO,*The power of convex relaxation: near-optimial matrix completion*, IEEE Transactions on Information Theory, 56(5) (2009), pp. 2053-2080. MR**2723472****10.**C. H. CHEN, B. S. HE AND X. M. YUAN,*Matrix completion via alternating direction methods*, IMA Journal of Numerical Analysis, to appear.**11.**P. L. COMBETTES AND V. R. WAJS,*Signal recovery by proximal forward-backward splitting*, Multiscale Model. Simul., 4 (2005), pp. 1168-1200. MR**2203849 (2007g:94016)****12.**J. ECKSTEIN AND M. FUKUSHIMA,*Some reformulation and applications of the alternating directions method of multipliers*, In: Hager, W. W.*et al.*eds., Large Scale Optimization: State of the Art, Kluwer Academic Publishers, pp. 115-134, 1994. MR**1307168****13.**E. ESSER,*Applications of Lagrangian-based alternating direction methods and connections to split Bregman*, preprint, available at`http://www.math.ucla.edu/applied/cam/`, 2009.**14.**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-4739.**15.**M. FUKUSHIMA,*Application of the alternating direction method of multipliers to separable convex programming problems*, Computational Optimization and Applications, 1(1992), pp. 93-111. MR**1195631 (94a:90020)****16.**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-331, 1983.**17.**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-40.**18.**R. GLOWINSKI AND P. LE TALLEC, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics, SIAM Studies in Applied Mathematics, Philadelphia, PA, 1989. MR**1060954 (91f:73038)****19.**T. GOLDSTEIN AND S. OSHER,*The split Bregman method for L1-regularized problems*, SIAM Journal on Imaging Science, 2(2) (2009), pp. 323-343. MR**2496060 (2010e:65087)****20.**E. HALE, W. YIN AND Y. ZHANG,*Fixed-point continuation for -minimization: methodology and convergence*, SIAM Journal on Optimization, 19(3) (2008), pp.1107-1130. MR**2460734 (2009j:90070)****21.**B. S. HE, L. Z. LIAO, D. HAN AND H. YANG,*A new inexact alternating directions method for monontone variational inequalities*, Mathematical Programming, 92(2002), pp. 103-118. MR**1892298 (2003b:90111)****22.**B. S. HE, M. H. XU AND X. M. YUAN,*Solving large-scale least squares semidefinite programming by alternating direction methods*, SIAM Journal on Matrix Analysis and Applications, 32(1) (2011), pp. 136-152. MR**2811295****23.**B. S. HE AND H. YANG,*Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities*, Operations Research Letters, 23 (1998), pp. 151-161. MR**1677664 (2000d:90089)****24.**B. S. HE, H. YANG AND S. L. WANG,*Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities*, Journal of Optimization theory and applications, 106 (2000), pp. 337-356. MR**1788928 (2001h:49016)****25.**M. R. HESTENES,*Multiplier and gradient methods*, Journal of Optimization Theory and Applications, 4 (1969), pp. 303-320. MR**0271809 (42:6690)****26.**S. JI AND J. YE,*An accelerated gradient method for trace norm minimization*, The Twenty-Sixth International Conference on Machine Learning, 2009.**27.**S. KONTOGIORGIS AND R. R. MEYER,*A variable-penalty alternating directions method for convex optimization*, Mathematical Programming, 83(1998), pp. 29-53. MR**1643963 (99k:90116)****28.**R. M. LARSEN,*PROPACK-Software for large and sparse SVD calculations*, Available at:`http://sun.stanfor.edu/srmunk/PROPACK/`, 2005.**29.**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.**30.**J. LIU, S. JI AND J. YE,*SLEP: A Sparse Learning Package*, Version 2.0, Available at:`http://www.public.asu.edu/~jye02/Software/SLEP`, 2010.**31.**Y. J. LIU, D. F. SUN AND K. C. TOH,*An implementable proximal point algorithmic framework for nuclear norm minimization*, Mathematical Programming, to appear.**32.**S. Q. MA, D. GOLDFARB AND L. CHEN,*Fixed point and Bregman iterative methods for matrix rank minimization*, Math. Program., 128 (2011), 321-353. MR**2810961****33.**Y. E. NESTEROV,*A method for unconstrained convex minimization problem with the rate of convergence*, Doklady AN SSSR, 269, pp. 543-547, 1983. MR**701288 (84i:90119)****34.**Y. E. NESTEROV,*Smooth minimization of nonsmooth functions*, Mathematical Programming, 103 (2005), pp. 127-152. MR**2166537 (2006g:90174)****35.**M. K. NG, P. A. WEISS AND X. M. YUAN,*Solving constrained total-variation problems via alternating direction methods*, SIAM Journal on Scientifc Computing, 32(5) (2010), pp. 2710-2736. MR**2684734 (2011i:65065)****36.**G. OBOZINSKI, B. TASKAR AND M. I. JORDAN,*Joint covariate selection and joint subspace selection for multiple classification problems*, Statistics and Computing, 2009. MR**2610775****37.**S. OSHER, M. BURGER, D. GOLDFARB, J. XU AND W. YIN,*An iterative regularization method for total variation-based image restoration*, Multiscale Model. Simul. 4(2) (2005), pp. 460-489. MR**2162864 (2006c:49051)****38.**T. K. PONG, P. TSENG, S. JI. AND J. YE,*Trace norm regularization: reformulations, algorithms, and multi-task learning*, SIAM Journal on Optimization, 20 (2010), pp. 3465-3489. MR**2763512****39.**M. J. D. POWELL,*A method for nonlinear constraints in minimization problems*, in Optimization, R. Fletcher, ed., Academic Press, New York, NY, pp. 283-298, 1969. MR**0272403 (42:7284)****40.**B. RECHT, M. FAZEL AND P. A. PARRILO,*Guaranteed minimum rank solutions to linear matrix equations via nuclear norm minimization*, SIAM Review, 52(2010), pp. 471-501. MR**2680543****41.**R. T. ROCKAFELLAR, Convex Analysis, Princeton University Press, Princeton, NJ, 1970. MR**0274683 (43:445)****42.**R. T. ROCKAFELLAR,*Augmented Lagrangians and applications of the proximal point algorithm in convex programming*, Mathematics of Operations Research, 1 (1976), 97-116. MR**0418919 (54:6954)****43.**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.**44.**N. SREBRO, J. D. M. RENNIE AND T. S. JAAKKOLA,*Maximum-margin matrix factorization*, Advances in Neural Information Processing System, (2005), pp. 1329-1336.**45.**J. F. STURM,*Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones*, Optimization Methods and Software 11 & 12 (1999), pp. 625-653. MR**1778433****46.**W. Y. SUN AND Y. X. YUAN,*Optimization theory and methods*, Nonlinear Programming Series: Springer Optimization and Its Applications, 2006. MR**2232297 (2007c:90002)****47.**J. SUN AND S. ZHANG,*A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs*, European Journal of Operational Research, 207 (2010), pp. 1210-1220. MR**2727074****48.**M. TAO AND X. M. YUAN,*Recovering low-rank and sparse components of matrices from incomplete and noisy observations*, SIAM Journal on Optimization, 21(1) (2011), pp. 57-81. MR**2765489****49.**K. C. TOH AND S. YUN,*An accelerated proximal gradient algorithm for nuclear norm regularized least suqares problems*, Pacific Journal of Optimization, 6(2010), pp. 615-640. MR**2743047****50.**P. TSENG,*Alternating projection-proximal methods for convex programming and variational inequalities*, SIAM Journal on Optimization, 7(1997), pp. 951-965. MR**1479608 (99a:90156)****51.**R. H. T¨UTÜNCÜ, K. C. TOH AND M. J. TODD,*Solving semidefinite-quadrtic-linear programs using SDPT3*, Mathematical Programming, 95(2003), pp. 189-217. MR**1976479 (2004c:90036)****52.**G. A. WATSON,*Characterization of the subdifferential of some matrix norms*, Linear Algebra and its Applications, 170 (1992), pp. 33-45. MR**1160950 (93b:15031)****53.**Z. W. WEN, D. GOLDFARB AND W. YIN,*Alternating direction augmented Lagrangina methods for semidefinite programming*, Mathematical Programming Computation, 2 (2010), pp. 203-230. MR**2741485****54.**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.**55.**J.-F. YANG AND Y. ZHANG,*Alternating direction method for -problems in compressive sensing*, SIAM Journal on Scientific Computing, 33(1) (2011), pp. 250-278. MR**2783194****56.**W. YIN,*Analysis and generalizations of the linearized Bregman method*, SIAM Journal on Imaging Sciences, 3(4) (2010), pp. 856-877. MR**2735964 (2011j:68172)****57.**W. YIN, S. OSHER, D. GOLDFARB, AND J. DARBON,*Bregman iterative algorithms for -minimization with applications to compressed sensing*. SIAM Journal on Imaging Science, 1 (2008), pp. 143-168. MR**2475828 (2010f:90170)****58.**X. ZHANG, M. BURGER, X. BRESSON AND S. OSHER,*Bregmanized Nonlocal Regularization for Deconvolution and Sparse Reconstruction*, SIAM Journal on Imaging Science, 3(2010), pp. 253-276. MR**2679428**

Retrieve articles in *Mathematics of Computation*
with MSC (2010):
90C25,
90C06,
65K05

Retrieve articles in all journals with MSC (2010): 90C25, 90C06, 65K05

Additional Information

**Junfeng Yang**

Affiliation:
Department of Mathematics, Nanjing University, 22 Hankou Road, Nanjing, 210093, People’s Republic of China.

Email:
jfyang@nju.edu.cn

**Xiaoming Yuan**

Affiliation:
Department of Mathematics, Hong Kong Baptist University, Hong Kong, People’s Republic of China.

Email:
xmyuan@hkbu.edu.hk

DOI:
https://doi.org/10.1090/S0025-5718-2012-02598-1

Keywords:
Convex programming,
nuclear norm,
low-rank,
augmented Lagrangian method,
alternating direction method,
linearized

Received by editor(s):
July 30, 2010

Received by editor(s) in revised form:
April 18, 2011, and August 9, 2011

Published electronically:
March 28, 2012

Additional Notes:
The work of the first author was supported by the Natural Science Foundation of China NSFC-11001123 and the Fundamental Research Funds for the Central Universities (Grant No. 1117020305).

The work of the second author was supported by the Hong Kong General Research Fund HKBU-202610.

Article copyright:
© Copyright 2012
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.