Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction
From MaRDI portal
Publication:5266366
DOI10.1137/15M1027528zbMATH Open1364.90278DBLPjournals/siamis/YangPC17arXiv1506.07029OpenAlexW2964011556WikidataQ57511146 ScholiaQ57511146MaRDI QIDQ5266366FDOQ5266366
Authors: Lei Yang, Ting Kei Pong, Xiaojun Chen 
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
Recommendations
- Global convergence of ADMM in nonconvex nonsmooth optimization
- Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure
- Convergence of ADMM for optimization problems with nonseparable nonconvex objective and linear constraints
- Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
- Inertial alternating direction method of multipliers for non-convex non-smooth optimization
alternating direction method of multipliersnonsmooth and nonconvex optimizationbackground/foreground extractiondual step-size
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
- 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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- 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)
- Splitting augmented Lagrangian-type algorithms with partial quadratic approximation to solve sparse signal recovery problems
- 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
- Robust tensor completion: equivalent surrogates, error bounds, and algorithms
- Two-stage convex relaxation approach to low-rank and sparsity regularized least squares loss
- Blind Ptychographic Phase Retrieval via Convergent Alternating Direction Method of Multipliers
- The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates
- The alternating direction method of multipliers for finding the distance between ellipsoids
- Multi-channel Potts-based reconstruction for multi-spectral computed tomography
- 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 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
- A splitting scheme for flip-free distortion energies
- 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
- 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
- An extended proximal ADMM algorithm for three-block nonconvex optimization problems
- A three-operator splitting algorithm for nonconvex sparsity regularization
- 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
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)
