Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization

By Junfeng Yang, Xiaoming Yuan. 2012

429 citations recorded by the source corpus.

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

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, methodology): “(2)An example of approximate minimization is taking one proximal gradient step, as used for example, in the Linearized ADMM algorithm (Goldfarb et al., 2013; Yang and Yuan, 2013).”
DP-ADMM: ADMM-Based Distributed Learning With Differential Privacy (2018, methodology): “Linearized ADMM [24], [25] replaces the quadratic function in the augmented Lagrangian function with a linearized approximation and thus provides a better way to solve subproblems without closedform solutions.”
Stochastic Alternating Direction Method of Multipliers (2013, methodology): “Besides that, many variations of this classical method have been recently developed, such as linearized (Goldfarb et al., 2010; Zhang et al., 2011; Yang & Yuan, 2012), accelerated (Goldfarb et al., 2010) and online (Wang & Banerjee, 2012) ADMM.”
Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation (2011, methodology): “The parameters of ADM and LADM are the same as that in [13] and [21], respectiv ely.”
A primal-dual algorithm with optimal stepsizes and its application in decentralized consensus optimization (2017, background): “Note that the step in (6a) can be written as arg min In [23], positive-deﬁniteness of I − ( γ/β ) AA ⊤ is required for proving the convergence.”
A Simple Prior-Free Method for Non-rigid Structure-from-Motion Factorization (2012, methodology): “Recent progress in compressive sensing and matrix completion such as SVT without SVD (Cai and Osher 2010) and alternating direction method (ADM) (Lin et al. 2010; Yang and Yuan 2013) can be used to further speed up the implementation.”
Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, methodology): “Moreover, Yuan et al. [438] developed a noise and a blur and noise nuclear-norm-free models SPCP which are detailed in Section 2.2.4.”
Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization (2013, methodology): “In the traditional ADMM [46] and linearized ADMM approaches [38], the penalty parameter is fixed.”