Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems

DOI10.1137/16M1064064zbMATH Open1358.90109arXiv1702.02505MaRDI QIDQ3179622FDOQ3179622

Thomas Pock, Shoham Sabach

Publication date: 19 December 2016

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

Abstract: In this paper we study nonconvex and nonsmooth optimization problems with semi-algebraic data, where the variables vector is split into several blocks of variables. The problem consists of one smooth function of the entire variables vector and the sum of nonsmooth functions for each block separately. We analyze an inertial version of the Proximal Alternating Linearized Minimization (PALM) algorithm and prove its global convergence to a critical point of the objective function at hand. We illustrate our theoretical findings by presenting numerical experiments on blind image deconvolution, on sparse non-negative matrix factorization and on dictionary learning, which demonstrate the viability and effectiveness of the proposed method.

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

Recommendations

• A Gauss-Seidel type inertial proximal alternating linearized minimization for a class of nonconvex optimization problems
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• iPiano: inertial proximal algorithm for nonconvex optimization
• Inertial proximal alternating minimization for nonconvex and nonsmooth problems
• On the rate of convergence of the proximal alternating linearized minimization algorithm for convex problems

zbMATH Keywords

blind image deconvolutiondictionary learningblock coordinate descentalternating minimizationsparse nonnegative matrix factorizationheavy ball methodnonconvex and nonsmooth minimizationKurdyka-Łojasiewicz property

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• iPiano: inertial proximal algorithm for nonconvex optimization
• $rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Variational Analysis
• Title not available (Why is that?)
• On the limited memory BFGS method for large scale optimization
• Introductory lectures on convex optimization. A basic course.
• Learning the parts of objects by non-negative matrix factorization
• 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
• Signal Recovery by Proximal Forward-Backward Splitting
• Title not available (Why is that?)
• Proximité et dualité dans un espace hilbertien
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• Performance of first-order methods for smooth convex minimization: a novel approach
• Some methods of speeding up the convergence of iteration methods
• Heavy-ball method in nonconvex optimization problems
• A globally convergent algorithm for nonconvex optimization based on block coordinate update

Cited In (72)

• Bregman proximal gradient algorithms for deep matrix factorization
• Splines for image metamorphosis
• Approximate versions of proximal iteratively reweighted algorithms including an extended IP-ICMM for signal and image processing problems
• Variational networks: an optimal control approach to early stopping variational methods for image restoration
• A Proximal Minimization Algorithm for Structured Nonconvex and Nonsmooth Problems
• Variational models for color image correction inspired by visual perception and neuroscience
• Unifying Abstract Inexact Convergence Theorems and Block Coordinate Variable Metric iPiano
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• Inertial accelerated SGD algorithms for solving large-scale lower-rank tensor CP decomposition problems
• Inertial stochastic PALM and applications in machine learning
• Inertial alternating generalized forward-backward splitting for image colorization
• iPiano: inertial proximal algorithm for nonconvex optimization
• A generalized inertial proximal alternating linearized minimization method for nonconvex nonsmooth problems
• Some accelerated alternating proximal gradient algorithms for a class of nonconvex nonsmooth problems
• Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons
• Nested alternating minimization with FISTA for non-convex and non-smooth optimization problems
• Image morphing in deep feature spaces: theory and applications
• Local convergence of the heavy-ball method and iPiano for non-convex optimization
• Deep Learning--Based Dictionary Learning and Tomographic Image Reconstruction
• Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems
• Convergence of inexact quasisubgradient methods with extrapolation
• Acceleration and Global Convergence of a First-Order Primal-Dual Method for Nonconvex Problems
• A Gauss-Seidel type inertial proximal alternating linearized minimization for a class of nonconvex optimization problems
• A variational proximal alternating linearized minimization in a given metric for limited-angle CT image reconstruction
• Iteratively reweighted \(\ell _1\) algorithms with extrapolation
• Choose Your Path Wisely: Gradient Descent in a Bregman Distance Framework
• A block inertial Bregman proximal algorithm for nonsmooth nonconvex problems with application to symmetric nonnegative matrix tri-factorization
• Multi-Instance Dimensionality Reduction via Sparsity and Orthogonality
• Block Bregman Majorization Minimization with Extrapolation
• Non-convex split Feasibility problems: models, algorithms and theory
• A variational model for deformable registration of uni-modal medical images with intensity biases
• Novel Proximal Gradient Methods for Nonnegative Matrix Factorization with Sparsity Constraints
• An inertial alternating minimization with Bregman distance for a class of nonconvex and nonsmooth problems
• An alternating structure-adapted Bregman proximal gradient descent algorithm for constrained nonconvex nonsmooth optimization problems and its inertial variant
• Alternating Structure-Adapted Proximal Gradient Descent for Nonconvex Nonsmooth Block-Regularized Problems
• A new proximal iterative hard thresholding method with extrapolation for \(\ell _0\) minimization
• Modern regularization methods for inverse problems
• The convergence properties of infeasible inexact proximal alternating linearized minimization
• 3D fluid flow estimation with integrated particle reconstruction
• Convex-Concave Backtracking for Inertial Bregman Proximal Gradient Algorithms in Nonconvex Optimization
• A Generative Variational Model for Inverse Problems in Imaging
• PCA reduced Gaussian mixture models with applications in superresolution
• Inertial proximal incremental aggregated gradient method with linear convergence guarantees
• Two-step inertial Bregman alternating minimization algorithm for nonconvex and nonsmooth problems
• Regularization of inverse problems via time discrete geodesics in image spaces
• An inertial proximal alternating direction method of multipliers for nonconvex optimization
• An inertial Bregman generalized alternating direction method of multipliers for nonconvex optimization
• Inertial alternating direction method of multipliers for non-convex non-smooth optimization
• Column $\ell_{2,0}$-Norm Regularized Factorization Model of Low-Rank Matrix Recovery and Its Computation
• A Stochastic Proximal Alternating Minimization for Nonsmooth and Nonconvex Optimization
• A convex variational model for learning convolutional image atoms from incomplete data
• An inertial projection and contraction algorithm for pseudomonotone variational inequalities without Lipschitz continuity
• A class of modified accelerated proximal gradient methods for nonsmooth and nonconvex minimization problems
• Alternating block linearized Bregman iterations for regularized nonnegative matrix factorization
• A stochastic two-step inertial Bregman proximal alternating linearized minimization algorithm for nonconvex and nonsmooth problems
• A refined inertial DC algorithm for DC programming
• Extrapolated plug-and-play three-operator splitting methods for nonconvex optimization with applications to image restoration
• An inertial ADMM for a class of nonconvex composite optimization with nonlinear coupling constraints
• A nonmonotone accelerated proximal gradient method with variable stepsize strategy for nonsmooth and nonconvex minimization problems
• Orthogonal nonnegative matrix factorization problems for clustering: a new formulation and a competitive algorithm
• A customized inertial proximal alternating minimization for SVD-free robust principal component analysis
• A globally convergent inertial first-order optimization method for multidimensional scaling
• Sequential inertial linear ADMM algorithm for nonconvex and nonsmooth multiblock problems with nonseparable structure
• Title not available (Why is that?)
• Template-based image reconstruction facing different topologies
• Convergence of Random Reshuffling under the Kurdyka–Łojasiewicz Inequality
• Analysis of a variable metric block coordinate method under proximal errors
• A unified Bregman alternating minimization algorithm for generalized DC programs with application to imaging
• A framelet sparse reconstruction method for pansharpening with guaranteed convergence
• Stochastic Gauss-Seidel type inertial proximal alternating linearized minimization and its application to proximal neural networks
• A new proximal heavy ball inexact line-search algorithm
• Linear Convergence of a Proximal Alternating Minimization Method with Extrapolation for \(\boldsymbol{\ell_1}\) -Norm Principal Component Analysis

Uses Software

• L-BFGS
• iPiano

This page was built for publication: Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems

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