Alternating Direction Method of Multipliers for a Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction

DOI10.1137/15M1027528zbMATH Open1364.90278DBLPjournals/siamis/YangPC17arXiv1506.07029OpenAlexW2964011556WikidataQ57511146 ScholiaQ57511146MaRDI QIDQ5266366FDOQ5266366

Lei Yang, Xiaojun Chen, Ting Kei Pong

Publication date: 2 June 2017

Published in: SIAM Journal on Imaging Sciences (Search for Journal in Brave)

Abstract: In this paper, we study a general optimization model, which covers a large class of existing models for many applications in imaging sciences. To solve the resulting possibly nonconvex, nonsmooth and non-Lipschitz optimization problem, we adapt the alternating direction method of multipliers (ADMM) with a general dual step-size to solve a reformulation that contains three blocks of variables, and analyze its convergence. We show that for any dual step-size less than the golden ratio, there exists a computable threshold such that if the penalty parameter is chosen above such a threshold and the sequence thus generated by our ADMM is bounded, then the cluster point of the sequence gives a stationary point of the nonconvex optimization problem. We achieve this via a potential function specifically constructed for our ADMM. Moreover, we establish the global convergence of the whole sequence if, in addition, this special potential function is a Kurdyka-{L}ojasiewicz function. Furthermore, we present a simple strategy for initializing the algorithm to guarantee boundedness of the sequence. Finally, we perform numerical experiments comparing our ADMM with the proximal alternating linearized minimization (PALM) proposed in [5] on the background/foreground extraction problem with real data. The numerical results show that our ADMM with a nontrivial dual step-size is efficient.

Full work available at URL: https://arxiv.org/abs/1506.07029

zbMATH Keywords

alternating direction method of multipliersnonsmooth and nonconvex optimizationbackground/foreground extractiondual step-size

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Optimality conditions and duality in mathematical programming (90C46) Applications of mathematical programming (90C90) Nonconvex programming, global optimization (90C26)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Nearly unbiased variable selection under minimax concave penalty
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• Variational Analysis
• Benchmarking optimization software with performance profiles.
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Asymptotics for Lasso-type estimators.
• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
• Robust principal component analysis?
• Alternating direction method of multipliers for penalized zero-variance discriminant analysis
• Asymptotic properties of bridge estimators in sparse high-dimensional regression models
• Hankel matrix rank minimization with applications to system identification and realization
• A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
• Node-Based Learning of Multiple Gaussian Graphical Models
• Smoothing Nonlinear Conjugate Gradient Method for Image Restoration Using Nonsmooth Nonconvex Minimization
• Linearly Constrained Non-Lipschitz Optimization for Image Restoration
• Efficient Reconstruction of Piecewise Constant Images Using Nonsmooth Nonconvex Minimization
• Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming
• Robust PCA via Outlier Pursuit
• Alternating direction method with Gaussian back substitution for separable convex programming
• Deblurring Images
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Traditional and recent approaches in background modeling for foreground detection: an overview
• A Convergent $3$-Block Semi-Proximal ADMM for Convex Minimization Problems with One Strongly Convex Block
• Comments on «Wavelets in statistics: A review» by A. Antoniadis
• A class of linearized proximal alternating direction methods
• Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning
• Energy Minimization Methods
• Global convergence of ADMM in nonconvex nonsmooth optimization
• Global Convergence of Splitting Methods for Nonconvex Composite Optimization
• Median filtering‐based methods for static background extraction from surveillance video

Cited In (56)

• An efficient regularized PR splitting type algorithm for two-block nonconvex linear constrained programs in \(\ell_{1 / 2}\) regularized compressed sensing problems
• A partial Bregman ADMM with a general relaxation factor for structured nonconvex and nonsmooth optimization
• Nonconvex multi-period mean-variance portfolio optimization
• Learning the sparse prior: modern approaches
• Convergence of Peaceman-Rachford splitting method with Bregman distance for three-block nonconvex nonseparable optimization
• Bregman proximal linearized ADMM for minimizing separable sums coupled by a difference of functions
• A Proximal Minimization Algorithm for Structured Nonconvex and Nonsmooth Problems
• A Bregman-style partially symmetric alternating direction method of multipliers for nonconvex multi-block optimization
• Generalized singular value thresholding operator based nonconvex low-rank and sparse decomposition for moving object detection
• Two-stage convex relaxation approach to low-rank and sparsity regularized least squares loss
• A Splitting Scheme for Flip-Free Distortion Energies
• Blind Ptychographic Phase Retrieval via Convergent Alternating Direction Method of Multipliers
• The alternating direction method of multipliers for finding the distance between ellipsoids
• Multi-channel Potts-based reconstruction for multi-spectral computed tomography
• Splitting augmented Lagrangian-type algorithms with partial quadratic approximation to solve sparse signal recovery problems
• An efficient semi-proximal ADMM algorithm for low-rank and sparse regularized matrix minimization problems with real-world applications
• On the discontinuity of images recovered by noncovex nonsmooth regularized isotropic models with box constraints
• An incremental aggregated proximal ADMM for linearly constrained nonconvex optimization with application to sparse logistic regression problems
• Whiteness constraints in a unified variational framework for image restoration
• A regularized alternating direction method of multipliers for a class of nonconvex problems
• An efficient non-convex total variation approach for image deblurring and denoising
• Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization
• Proximal ADMM for nonconvex and nonsmooth optimization
• Cauchy noise removal by nonconvex ADMM with convergence guarantees
• Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
• Global convergence of ADMM in nonconvex nonsmooth optimization
• Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
• Fast algorithms for sparse portfolio selection considering industries and investment styles
• Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure
• Tractable ADMM schemes for computing KKT points and local minimizers for \(\ell_0\)-minimization problems
• A Three-Operator Splitting Algorithm for Nonconvex Sparsity Regularization
• A hybrid Bregman alternating direction method of multipliers for the linearly constrained difference-of-convex problems
• An ADMM-LAP method for total variation myopic deconvolution of adaptive optics retinal images
• Alternating direction method of multipliers for nonconvex fused regression problems
• A Symmetric Alternating Direction Method of Multipliers for Separable Nonconvex Minimization Problems
• A nonconvex model with minimax concave penalty for image restoration
• On the Edge Recovery Property of Noncovex Nonsmooth Regularization in Image Restoration
• The lower bound of nonlocal gradient for non-convex and non-smooth image patches based regularization
• Iterative \(p\)-shrinkage thresholding algorithm for low Tucker rank tensor recovery
• Low Tucker rank tensor recovery via ADMM based on exact and inexact iteratively reweighted algorithms
• Nonconvex optimization for robust tensor completion from grossly sparse observations
• The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates
• An improved total variation regularized RPCA for moving object detection with dynamic background
• Algorithm for overcoming the curse of dimensionality for time-dependent non-convex Hamilton-Jacobi equations arising from optimal control and differential games problems
• Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property
• Robust Tensor Completion: Equivalent Surrogates, Error Bounds, and Algorithms
• An extended proximal ADMM algorithm for three-block nonconvex optimization problems
• A new Lagrangian-based first-order method for nonconvex constrained optimization
• Convergence analysis of an ALF-based nonconvex splitting algorithm with SQP structure
• A nonconvex ADMM for a class of sparse inverse semidefinite quadratic programming problems
• An inertial proximal partially symmetric ADMM-based algorithm for linearly constrained multi-block nonconvex optimization problems with applications
• An inertial proximal alternating direction method of multipliers for nonconvex optimization
• Inertial alternating direction method of multipliers for non-convex non-smooth optimization
• A unified framework for nonconvex nonsmooth sparse and low-rank decomposition by majorization-minimization algorithm
• Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
• Least absolute deviations learning of multiple tasks

Uses Software

• BADMM

This page was built for publication: Alternating Direction Method of Multipliers for a Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5266366)