Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization. (English) Zbl 1263.90062

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


90C25 Convex programming
90C06 Large-scale problems in mathematical programming
65K05 Numerical mathematical programming methods
Full Text: DOI


[1] [Aber09] 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. · Zbl 1235.68122
[2] [Arg] A. Argyriou, T. Evgeniou and M. Pontil, Convex multi-task feature learning, Machine Learning, 73(3)(2008), pp. 243-272. · Zbl 1470.68073
[3] [BorLewis-03] J. M. Borwein, and A. S. Lewis, Convex analysis and nonlinear optimization, Springer-Verlag, 2003.
[4] [Cai] J. F. Cai, E. J. Cand\'es and Z. W. Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20(4) (2010), pp. 1956-1982. · Zbl 1201.90155
[5] [Cai-MC2] J. F. Cai, S. Osher and Z. Shen, Linearized Bregman iterations for compressed sensing, Mathematics of Computation, 78(267)(2009), pp. 1515-1536. · Zbl 1198.65102
[6] [Cai-MC] J. F. Cai, S. Osher and Z. Shen, Convergence of the Linearized Bregman Iteration for \(\ell_1\)-Norm Minimization, Mathematics of Computation, 78(268) (2009), pp. 2127-2136. · Zbl 1198.65103
[7] [Cai-MMS] 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. · Zbl 1189.94014
[8] [CandesRecht] E. J. Cand\`es and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9(2009), pp. 717-772. · Zbl 1219.90124
[9] [CandesTao] E. J. Cand\`es and T. Tao, The power of convex relaxation: near-optimial matrix completion, IEEE Transactions on Information Theory, 56(5) (2009), pp. 2053-2080. · Zbl 1366.15021
[10] [Chen-He-Yuan] C. H. Chen, B. S. He and X. M. Yuan, Matrix completion via alternating direction methods, IMA Journal of Numerical Analysis, to appear. · Zbl 1236.65043
[11] [ComW-05] 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
[12] [EcFuk] 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. · Zbl 0816.90109
[13] [Ess] E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split Bregman, preprint, available at \urlhttp://www.math.ucla.edu/applied/cam/, 2009.
[14] [Fazel2001] 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] [Fuk92] M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems, Computational Optimization and Applications, 1(1992), pp. 93-111. · Zbl 0763.90071
[16] [Ga83] 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] [GaMe] 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. · Zbl 0352.65034
[18] [Glt89] R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics, SIAM Studies in Applied Mathematics, Philadelphia, PA, 1989. · Zbl 0698.73001
[19] [Goldstein-Osher-09] T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems, SIAM Journal on Imaging Science, 2(2) (2009), pp. 323-343. · Zbl 1177.65088
[20] [FPC] E. Hale, W. Yin and Y. Zhang, Fixed-point continuation for \(\ell_1\)-minimization: methodology and convergence, SIAM Journal on Optimization, 19(3) (2008), pp.1107-1130. · Zbl 1180.65076
[21] [He02MP] 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. · Zbl 1009.90108
[22] [HeXuYuan] 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. · Zbl 1243.49039
[23] [HeYang97] 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. · Zbl 0963.49006
[24] [He00JOTA] 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. · Zbl 0997.49008
[25] [Hestenes69] M. R. Hestenes, Multiplier and gradient methods, Journal of Optimization Theory and Applications, 4 (1969), pp. 303-320. · Zbl 0174.20705
[26] [Ye] S. Ji and J. Ye, An accelerated gradient method for trace norm minimization, The Twenty-Sixth International Conference on Machine Learning, 2009.
[27] [KoMe] S. Kontogiorgis and R. R. Meyer, A variable-penalty alternating directions method for convex optimization, Mathematical Programming, 83(1998), pp. 29-53. · Zbl 0920.90118
[28] [Larsen] R. M. Larsen, PROPACK-Software for large and sparse SVD calculations, Available at: \urlhttp://sun.stanfor.edu/srmunk/PROPACK/, 2005.
[29] [LinCWM] 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] [SLEP] J. Liu, S. Ji and J. Ye, SLEP: A Sparse Learning Package, Version 2.0, Available at: \urlhttp://www.public.asu.edu/ jye02/Software/SLEP, 2010.
[31] [Liu-Sun-Toh-09] Y. J. Liu, D. F. Sun and K. C. Toh, An implementable proximal point algorithmic framework for nuclear norm minimization, Mathematical Programming, to appear. · Zbl 1262.90125
[32] [Ma] S. Q. Ma, D. Goldfarb and L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program., 128 (2011), 321-353. · Zbl 1221.65146
[33] [Nes83] Y. E. Nesterov, A method for unconstrained convex minimization problem with the rate of convergence \(O(1/k^2)\), Doklady AN SSSR, 269, pp. 543-547, 1983.
[34] [Nes05] Y. E. Nesterov, Smooth minimization of nonsmooth functions, Mathematical Programming, 103 (2005), pp. 127-152. · Zbl 1079.90102
[35] [NWY] 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. · Zbl 1217.65071
[36] [Obo] G. Obozinski, B. Taskar and M. I. Jordan, Joint covariate selection and joint subspace selection for multiple classification problems, Statistics and Computing, 2009.
[37] [Osher-etal] 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. · Zbl 1090.94003
[38] [Pang] 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. · Zbl 1211.90129
[39] [Powell69] 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.
[40] [Recht] 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. · Zbl 1198.90321
[41] [Rock1970] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401
[42] [Rock1976] R. T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Mathematics of Operations Research, 1 (1976), 97-116. · Zbl 0402.90076
[43] [Setzer2] 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] [Sre] 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] [Sturm99] 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. · Zbl 0973.90526
[46] [SunYuan] W. Y. Sun and Y. X. Yuan, Optimization theory and methods, Nonlinear Programming Series: Springer Optimization and Its Applications, 2006. · Zbl 1129.90002
[47] [SunZhang] 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. · Zbl 1229.90119
[48] [TaoYuan] 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. · Zbl 1218.90115
[49] [Toh] 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. · Zbl 1205.90218
[50] [Tseng97] P. Tseng, Alternating projection-proximal methods for convex programming and variational inequalities, SIAM Journal on Optimization, 7(1997), pp. 951-965. · Zbl 0914.90218
[51] [TuToh03] R. H. T\`“ut\'”unc\"u, K. C. Toh and M. J. Todd, Solving semidefinite-quadrtic-linear programs using SDPT3, Mathematical Programming, 95(2003), pp. 189-217. · Zbl 1030.90082
[52] [Watson-92] G. A. Watson, Characterization of the subdifferential of some matrix norms, Linear Algebra and its Applications, 170 (1992), pp. 33-45. · Zbl 0751.15011
[53] [Wen] Z. W. Wen, D. Goldfarb and W. Yin, Alternating direction augmented Lagrangina methods for semidefinite programming, Mathematical Programming Computation, 2 (2010), pp. 203-230. · Zbl 1206.90088
[54] [Wen-Yin-Zhang-10] 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] [YangZhang] J.-F. Yang and Y. Zhang, Alternating direction method for \(\ell_1\)-problems in compressive sensing, SIAM Journal on Scientific Computing, 33(1) (2011), pp. 250-278. · Zbl 1256.65060
[56] [Yin-Breg-Review] W. Yin, Analysis and generalizations of the linearized Bregman method, SIAM Journal on Imaging Sciences, 3(4) (2010), pp. 856-877. · Zbl 1211.68491
[57] [Yin-SIIMS08] W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman iterative algorithms for \(\ell_1\)-minimization with applications to compressed sensing. SIAM Journal on Imaging Science, 1 (2008), pp. 143-168. · Zbl 1203.90153
[58] [BOS] 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. · Zbl 1191.94030
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.