Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

References [Enhancements On Off] (What's this?)

Similar Articles

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.

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

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.

American Mathematical Society