Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization

Yang, Junfeng; Yuan, Xiaoming

doi:10.1090/S0025-5718-2012-02598-1

Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization
HTML articles powered by AMS MathViewer

by Junfeng Yang and Xiaoming Yuan PDF

Math. Comp. 82 (2013), 301-329 Request permission

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.

References

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.
A. Argyriou, T. Evgeniou and M. Pontil, Convex multi-task feature learning, Machine Learning, 73(3)(2008), pp. 243–272.
Jonathan M. Borwein and Adrian S. Lewis, Convex analysis and nonlinear optimization, 2nd ed., CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 3, Springer, New York, 2006. Theory and examples. MR 2184742, DOI 10.1007/978-0-387-31256-9
Jian-Feng Cai, Emmanuel J. Candès, and Zuowei Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim. 20 (2010), no. 4, 1956–1982. MR 2600248, DOI 10.1137/080738970
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Linearized Bregman iterations for compressed sensing, Math. Comp. 78 (2009), no. 267, 1515–1536. MR 2501061, DOI 10.1090/S0025-5718-08-02189-3
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Convergence of the linearized Bregman iteration for $\ell _1$-norm minimization, Math. Comp. 78 (2009), no. 268, 2127–2136. MR 2521281, DOI 10.1090/S0025-5718-09-02242-X
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Split Bregman methods and frame based image restoration, Multiscale Model. Simul. 8 (2009/10), no. 2, 337–369. MR 2581025, DOI 10.1137/090753504
Emmanuel J. Candès and Benjamin Recht, Exact matrix completion via convex optimization, Found. Comput. Math. 9 (2009), no. 6, 717–772. MR 2565240, DOI 10.1007/s10208-009-9045-5
Emmanuel J. Candès and Terence Tao, The power of convex relaxation: near-optimal matrix completion, IEEE Trans. Inform. Theory 56 (2010), no. 5, 2053–2080. MR 2723472, DOI 10.1109/TIT.2010.2044061
C. H. Chen, B. S. He and X. M. Yuan, Matrix completion via alternating direction methods, IMA Journal of Numerical Analysis, to appear.
Patrick L. Combettes and Valérie R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul. 4 (2005), no. 4, 1168–1200. MR 2203849, DOI 10.1137/050626090
Jonathan Eckstein and Masao Fukushima, Some reformulations and applications of the alternating direction method of multipliers, Large scale optimization (Gainesville, FL, 1993) Kluwer Acad. Publ., Dordrecht, 1994, pp. 115–134. MR 1307168
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.
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.
Masao Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems, Comput. Optim. Appl. 1 (1992), no. 1, 93–111. MR 1195631, DOI 10.1007/BF00247655
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.
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.
Roland Glowinski and Patrick Le Tallec, Augmented Lagrangian and operator-splitting methods in nonlinear mechanics, SIAM Studies in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1989. MR 1060954, DOI 10.1137/1.9781611970838
Tom Goldstein and Stanley Osher, The split Bregman method for $L1$-regularized problems, SIAM J. Imaging Sci. 2 (2009), no. 2, 323–343. MR 2496060, DOI 10.1137/080725891
Elaine T. Hale, Wotao Yin, and Yin Zhang, Fixed-point continuation for $l_1$-minimization: methodology and convergence, SIAM J. Optim. 19 (2008), no. 3, 1107–1130. MR 2460734, DOI 10.1137/070698920
Bingsheng He, Li-Zhi Liao, Deren Han, and Hai Yang, A new inexact alternating directions method for monotone variational inequalities, Math. Program. 92 (2002), no. 1, Ser. A, 103–118. MR 1892298, DOI 10.1007/s101070100280
Bingsheng He, Minghua Xu, and Xiaoming Yuan, Solving large-scale least squares semidefinite programming by alternating direction methods, SIAM J. Matrix Anal. Appl. 32 (2011), no. 1, 136–152. MR 2811295, DOI 10.1137/090761549
Bingsheng He and Hai Yang, Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities, Oper. Res. Lett. 23 (1998), no. 3-5, 151–161. MR 1677664, DOI 10.1016/S0167-6377(98)00044-3
B. S. He, H. Yang, and S. L. Wang, Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities, J. Optim. Theory Appl. 106 (2000), no. 2, 337–356. MR 1788928, DOI 10.1023/A:1004603514434
Magnus R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appl. 4 (1969), 303–320. MR 271809, DOI 10.1007/BF00927673
S. Ji and J. Ye, An accelerated gradient method for trace norm minimization, The Twenty-Sixth International Conference on Machine Learning, 2009.
Spyridon Kontogiorgis and Robert R. Meyer, A variable-penalty alternating directions method for convex optimization, Math. Programming 83 (1998), no. 1, Ser. A, 29–53. MR 1643963, DOI 10.1016/S0025-5610(97)00103-2
R. M. Larsen, PROPACK-Software for large and sparse SVD calculations, Available at: http://sun.stanfor.edu/srmunk/PROPACK/, 2005.
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.
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.
Y. J. Liu, D. F. Sun and K. C. Toh, An implementable proximal point algorithmic framework for nuclear norm minimization, Mathematical Programming, to appear.
Shiqian Ma, Donald Goldfarb, and Lifeng Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program. 128 (2011), no. 1-2, Ser. A, 321–353. MR 2810961, DOI 10.1007/s10107-009-0306-5
Yu. E. Nesterov, A method for solving the convex programming problem with convergence rate $O(1/k^{2})$, Dokl. Akad. Nauk SSSR 269 (1983), no. 3, 543–547 (Russian). MR 701288
Yu. Nesterov, Smooth minimization of non-smooth functions, Math. Program. 103 (2005), no. 1, Ser. A, 127–152. MR 2166537, DOI 10.1007/s10107-004-0552-5
Michael K. Ng, Pierre Weiss, and Xiaoming Yuan, Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods, SIAM J. Sci. Comput. 32 (2010), no. 5, 2710–2736. MR 2684734, DOI 10.1137/090774823
Guillaume Obozinski, Ben Taskar, and Michael I. Jordan, Joint covariate selection and joint subspace selection for multiple classification problems, Stat. Comput. 20 (2010), no. 2, 231–252. MR 2610775, DOI 10.1007/s11222-008-9111-x
Stanley Osher, Martin Burger, Donald Goldfarb, Jinjun Xu, and Wotao Yin, An iterative regularization method for total variation-based image restoration, Multiscale Model. Simul. 4 (2005), no. 2, 460–489. MR 2162864, DOI 10.1137/040605412
Ting Kei Pong, Paul Tseng, Shuiwang Ji, and Jieping Ye, Trace norm regularization: reformulations, algorithms, and multi-task learning, SIAM J. Optim. 20 (2010), no. 6, 3465–3489. MR 2763512, DOI 10.1137/090763184
M. J. D. Powell, A method for nonlinear constraints in minimization problems, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London, 1969, pp. 283–298. MR 0272403
Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev. 52 (2010), no. 3, 471–501. MR 2680543, DOI 10.1137/070697835
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683
R. T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res. 1 (1976), no. 2, 97–116. MR 418919, DOI 10.1287/moor.1.2.97
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.
N. Srebro, J. D. M. Rennie and T. S. Jaakkola, Maximum-margin matrix factorization, Advances in Neural Information Processing System, (2005), pp. 1329–1336.
Jos F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw. 11/12 (1999), no. 1-4, 625–653. Interior point methods. MR 1778433, DOI 10.1080/10556789908805766
Wenyu Sun and Ya-Xiang Yuan, Optimization theory and methods, Springer Optimization and Its Applications, vol. 1, Springer, New York, 2006. Nonlinear programming. MR 2232297
Jie Sun and Su Zhang, A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs, European J. Oper. Res. 207 (2010), no. 3, 1210–1220. MR 2727074, DOI 10.1016/j.ejor.2010.07.020
Min Tao and Xiaoming Yuan, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim. 21 (2011), no. 1, 57–81. MR 2765489, DOI 10.1137/100781894
Kim-Chuan Toh and Sangwoon Yun, An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pac. J. Optim. 6 (2010), no. 3, 615–640. MR 2743047
Paul Tseng, Alternating projection-proximal methods for convex programming and variational inequalities, SIAM J. Optim. 7 (1997), no. 4, 951–965. MR 1479608, DOI 10.1137/S1052623495279797
R. H. Tütüncü, K. C. Toh, and M. J. Todd, Solving semidefinite-quadratic-linear programs using SDPT3, Math. Program. 95 (2003), no. 2, Ser. B, 189–217. Computational semidefinite and second order cone programming: the state of the art. MR 1976479, DOI 10.1007/s10107-002-0347-5
G. A. Watson, Characterization of the subdifferential of some matrix norms, Linear Algebra Appl. 170 (1992), 33–45. MR 1160950, DOI 10.1016/0024-3795(92)90407-2
Zaiwen Wen, Donald Goldfarb, and Wotao Yin, Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput. 2 (2010), no. 3-4, 203–230. MR 2741485, DOI 10.1007/s12532-010-0017-1
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.
Junfeng Yang and Yin Zhang, Alternating direction algorithms for $\ell _1$-problems in compressive sensing, SIAM J. Sci. Comput. 33 (2011), no. 1, 250–278. MR 2783194, DOI 10.1137/090777761
Wotao Yin, Analysis and generalizations of the linearized Bregman model, SIAM J. Imaging Sci. 3 (2010), no. 4, 856–877. MR 2735964, DOI 10.1137/090760350
Wotao Yin, Stanley Osher, Donald Goldfarb, and Jerome Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci. 1 (2008), no. 1, 143–168. MR 2475828, DOI 10.1137/070703983
Xiaoqun Zhang, Martin Burger, Xavier Bresson, and Stanley Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, SIAM J. Imaging Sci. 3 (2010), no. 3, 253–276. MR 2679428, DOI 10.1137/090746379