Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization

DOI10.1090/S0025-5718-2012-02598-1zbMath1263.90062OpenAlexW2079558799MaRDI QIDQ4911905

Junfeng Yang, Xiao-Ming Yuan

Publication date: 20 March 2013

Published in: Mathematics of Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0025-5718-2012-02598-1

zbMATH Keywords

augmented Lagrangian methodalternating direction methodnuclear normlow-ranklinearized

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06)

Related Items

A proximal alternating direction method for \(\ell_{2,1}\)-norm least squares problem in multi-task feature learning ⋮ Linearized alternating direction method of multipliers for sparse group and fused Lasso models ⋮ Linearized symmetric multi-block ADMM with indefinite proximal regularization and optimal proximal parameter ⋮ A survey on some recent developments of alternating direction method of multipliers ⋮ The Moreau envelope based efficient first-order methods for sparse recovery ⋮ A General Inertial Proximal Point Algorithm for Mixed Variational Inequality Problem ⋮ A new accelerated positive-indefinite proximal ADMM for constrained separable convex optimization problems ⋮ Partial Error Bound Conditions and the Linear Convergence Rate of the Alternating Direction Method of Multipliers ⋮ Solving total-variation image super-resolution problems via proximal symmetric alternating direction methods ⋮ Inertial Proximal ADMM for Linearly Constrained Separable Convex Optimization ⋮ Iteration-complexity analysis of a generalized alternating direction method of multipliers ⋮ A proximal Peaceman-Rachford splitting method for compressive sensing ⋮ The developments of proximal point algorithms ⋮ A Proximal Strictly Contractive Peaceman--Rachford Splitting Method for Convex Programming with Applications to Imaging ⋮ Unnamed Item ⋮ Alternating proximal gradient method for convex minimization ⋮ Enhanced low-rank representation via sparse manifold adaption for semi-supervised learning ⋮ Convergence analysis of positive-indefinite proximal ADMM with a Glowinski's relaxation factor ⋮ A primal Douglas-Rachford splitting method for the constrained minimization problem in compressive sensing ⋮ An approximation method of CP rank for third-order tensor completion ⋮ Seismic data reconstruction via weighted nuclear-norm minimization ⋮ Inertial generalized proximal Peaceman-Rachford splitting method for separable convex programming ⋮ Manifold regularized matrix completion for multi-label learning with ADMM ⋮ Inter-class sparsity based discriminative least square regression ⋮ An accelerated proximal augmented Lagrangian method and its application in compressive sensing ⋮ A generalized inexact Uzawa method for stable principal component pursuit problem with nonnegative constraints ⋮ Nonexpansiveness of a linearized augmented Lagrangian operator for hierarchical convex optimization ⋮ Multi-step inertial strictly contractive PRSM algorithms for convex programming problems with applications ⋮ A unified primal-dual algorithm framework for inequality constrained problems ⋮ On relaxation of some customized proximal point algorithms for convex minimization: from variational inequality perspective ⋮ A golden ratio proximal alternating direction method of multipliers for separable convex optimization ⋮ Proximal linearization methods for Schatten \(p\)-quasi-norm minimization ⋮ A proximal fully parallel splitting method with a relaxation factor for separable convex programming ⋮ Image restoration based on the hybrid total-variation-type model ⋮ Discriminative sparse least square regression for semi-supervised learning ⋮ A generalization of linearized alternating direction method of multipliers for solving two-block separable convex programming ⋮ A generalized forward-backward splitting operator: degenerate analysis and applications ⋮ Convergence study on the proximal alternating direction method with larger step size ⋮ Accelerated low rank matrix approximate algorithms for matrix completion ⋮ The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates ⋮ Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization ⋮ A dual-primal balanced augmented Lagrangian method for linearly constrained convex programming ⋮ Splitting and linearizing augmented Lagrangian algorithm for subspace recovery from corrupted observations ⋮ A new nonconvex approach to low-rank matrix completion with application to image inpainting ⋮ Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework ⋮ Fused Lasso penalized least absolute deviation estimator for high dimensional linear regression ⋮ Modified alternating direction methods for the modified multiple-sets split feasibility problems ⋮ An implementable first-order primal-dual algorithm for structured convex optimization ⋮ Linear total variation approximate regularized nuclear norm optimization for matrix completion ⋮ Properties and methods for finding the best rank-one approximation to higher-order tensors ⋮ Multiplicative denoising based on linearized alternating direction method using discrepancy function constraint ⋮ An alternating direction method of multipliers with a worst-case $O(1/n^2)$ convergence rate ⋮ A linearized Peaceman-Rachford splitting method for structured convex optimization with application to stable principal component pursuit ⋮ Nuclear norm based two-dimensional sparse principal component analysis ⋮ Conditional gradient algorithms for norm-regularized smooth convex optimization ⋮ A fast proximal point algorithm for \(\ell_{1}\)-minimization problem in compressed sensing ⋮ Convergent prediction-correction-based ADMM for multi-block separable convex programming ⋮ Robust bilinear factorization with missing and grossly corrupted observations ⋮ Estimation of Graphical Models through Structured Norm Minimization ⋮ An extragradient-based alternating direction method for convex minimization ⋮ TGV-based multiplicative noise removal approach: models and algorithms ⋮ An alternating direction algorithm for matrix completion with nonnegative factors ⋮ Low-rank and sparse matrices fitting algorithm for low-rank representation ⋮ Median filtering‐based methods for static background extraction from surveillance video ⋮ A simple and efficient algorithm for fused lasso signal approximator with convex loss function ⋮ A new linearized split Bregman iterative algorithm for image reconstruction in sparse-view X-ray computed tomography ⋮ A prediction-correction-based primal-dual hybrid gradient method for linearly constrained convex minimization ⋮ New convergence analysis of a primal-dual algorithm with large stepsizes ⋮ Convergence study on strictly contractive peaceman-Rachford splitting method for nonseparable convex minimization models with quadratic coupling terms ⋮ Implementing the Alternating Direction Method of Multipliers for Big Datasets: A Case Study of Least Absolute Shrinkage and Selection Operator ⋮ A class of ADMM-based algorithms for three-block separable convex programming ⋮ A class of customized proximal point algorithms for linearly constrained convex optimization ⋮ A penalty decomposition method for rank minimization problem with affine constraints ⋮ Linear Convergence of the Alternating Direction Method of Multipliers for a Class of Convex Optimization Problems ⋮ Linearized alternating directions method for \(\ell_1\)-norm inequality constrained \(\ell_1\)-norm minimization ⋮ A partially parallel splitting method for multiple-block separable convex programming with applications to robust PCA ⋮ Generalized alternating direction method of multipliers: new theoretical insights and applications ⋮ A generalized projective reconstruction theorem and depth constraints for projective factorization ⋮ A simple prior-free method for non-rigid structure-from-motion factorization ⋮ A new smoothed L0 regularization approach for sparse signal recovery ⋮ Block-wise Alternating Direction Method of Multipliers for Multiple-block Convex Programming and Beyond ⋮ Optimally linearizing the alternating direction method of multipliers for convex programming ⋮ On the iteration-complexity of a non-Euclidean hybrid proximal extragradient framework and of a proximal ADMM ⋮ Inertial proximal strictly contractive peaceman-Rachford splitting method with an indefinite term for convex optimization ⋮ Scalable Robust Matrix Recovery: Frank--Wolfe Meets Proximal Methods ⋮ Strictly contractive Peaceman-Rachford splitting method to recover the corrupted low rank matrix ⋮ Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization ⋮ An alternate minimization method beyond positive definite proximal regularization: convergence and complexity ⋮ An Inexact Uzawa Algorithmic Framework for Nonlinear Saddle Point Problems with Applications to Elliptic Optimal Control Problem ⋮ A stochastic alternating direction method of multipliers for non-smooth and non-convex optimization ⋮ An inexact symmetric ADMM algorithm with indefinite proximal term for sparse signal recovery and image restoration problems ⋮ Convergence analysis of an inexact three-operator splitting algorithm ⋮ A modified primal-dual method with applications to some sparse recovery problems ⋮ On the pointwise iteration-complexity of a dynamic regularized ADMM with over-relaxation stepsize ⋮ LINEARIZED ALTERNATING DIRECTION METHOD OF MULTIPLIERS FOR SEPARABLE CONVEX OPTIMIZATION OF REAL FUNCTIONS IN COMPLEX DOMAIN ⋮ An Overview of Computational Sparse Models and Their Applications in Artificial Intelligence ⋮ Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning ⋮ An alternating direction method with continuation for nonconvex low rank minimization ⋮ Convergence analysis of L-ADMM for multi-block linear-constrained separable convex minimization problem ⋮ A revisit of Chen-Teboulle's proximal-based decomposition method ⋮ A singular value shrinkage thresholding algorithm for folded concave penalized low-rank matrix optimization problems ⋮ Solving monotone inclusions involving the sum of three maximally monotone operators and a cocoercive operator with applications ⋮ An extended linearized alternating direction method of multipliers for fused-Lasso penalized linear regression

Uses Software

• SeDuMi
• SDPT3
• PROPACK
• LMaFit
• SLEP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving semidefinite-quadratic-linear programs using SDPT3
• Smooth minimization of non-smooth functions
• An implementable proximal point algorithmic framework for nuclear norm minimization
• Fixed point and Bregman iterative methods for matrix rank minimization
• A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs
• Alternating direction augmented Lagrangian methods for semidefinite programming
• Convex multi-task feature learning
• Characterization of the subdifferential of some matrix norms
• Application of the alternating direction method of multipliers to separable convex programming problems
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• A variable-penalty alternating directions method for convex optimization
• Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities
• Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities
• A new inexact alternating directions method for monotone variational inequalities
• Optimization theory and methods. Nonlinear programming
• Multiplier and gradient methods
• Exact matrix completion via convex optimization
• Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
• Solving Constrained Total-variation Image Restoration and Reconstruction Problems via Alternating Direction Methods
• Analysis and Generalizations of the Linearized Bregman Method
• Linearized Bregman iterations for compressed sensing
• Convergence of the linearized Bregman iteration for ℓ₁-norm minimization
• A Singular Value Thresholding Algorithm for Matrix Completion
• Trace Norm Regularization: Reformulations, Algorithms, and Multi-Task Learning
• Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing
• Matrix completion via an alternating direction method
• The Split Bregman Method for L1-Regularized Problems
• Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
• Split Bregman Methods and Frame Based Image Restoration
• Bregmanized Nonlocal Regularization for Deconvolution and Sparse Reconstruction
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Alternating Projection-Proximal Methods for Convex Programming and Variational Inequalities
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
• Signal Recovery by Proximal Forward-Backward Splitting
• Convex Analysis
• An Iterative Regularization Method for Total Variation-Based Image Restoration
• Navigating in a Graph by Aid of Its Spanning Tree Metric