Preconditioning of a generalized forward-backward splitting and application to optimization on graphs

DOI10.1137/15M1018253MaRDI QIDQ2797758zbMATH OpenOpenAlexFDO

Authors Hugo Raguet, Loïc Landrieu

Publication date 31 March 2016

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

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

zbMATH Keywords

aggregating spatial statisticsforward-backward splittinggraph learningmonotone operator splittingnonsmooth convex optimizationpreconditioningtotal variation

Mathematics Subject Classification ID

Applications of operator theory in optimization, convex analysis, mathematical programming, economics (47N10) Directional data; spatial statistics (62H11) Convex programming (90C25) Mathematical geography and demography (91D20) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Abstract: We present a preconditioning of a generalized forward-backward splitting algorithm for finding a zero of a sum of maximally monotone operators $su{m}_{i=1}^n{A}_i+B$ with $B$ cocoercive, involving only the computation of $B$ and of the resolvent of each $A_i$ separately. This allows in particular to minimize functionals of the form $su{m}_{i=1}^n{g}_i+f$ with $f$ smooth, using only the computation of the gradient of $f$ and of the proximity operator of each $g_i$ separately. By adapting the underlying metric, such preconditioning can serve two practical purposes: first, it might accelerate the convergence, or second, it might simplify the computation of the resolvent of $A_i$ for some $i$. In addition, in many cases of interest, our preconditioning strategy allows the economy of storage and computation concerning some auxiliary variables. In particular, we show how this approach can handle large-scale, nonsmooth, convex optimization problems structured on graphs, which arises in many image processing or learning applications, and that it compares favorably to alternatives in the literature.

Recommendations

• A generalized forward-backward splitting
• A preconditioning technique for first-order primal-dual splitting method in convex optimization
• A new preconditioning algorithm for finding a zero of the sum of two monotone operators and its application to image restoration problems
• Preconditioned three-operator splitting algorithm with applications to image restoration
• A proximal point analysis of the preconditioned alternating direction method of multipliers

Cites work

• A Class of Inexact Variable Metric Proximal Point Algorithms
• A class of randomized primal-dual algorithms for distributed optimization
• A class of variable metric decomposition methods for monotone variational inclusions
• A family of variable metric proximal methods
• A first-order primal-dual algorithm for convex problems with applications to imaging
• A generalized forward-backward splitting
• A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings
• A preconditioning proximal Newton method for nondifferentiable convex optimization
• A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
• A splitting algorithm for dual monotone inclusions involving cocoercive operators
• A Variable Metric Extension of the Forward–Backward–Forward Algorithm for Monotone Operators
• A Variable Metric Proximal Point Algorithm for Monotone Operators
• An inertial forward-backward algorithm for monotone inclusions
• Compositions and convex combinations of averaged nonexpansive operators
• Constrained Delaunay triangulations
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Convergence Rates in Forward--Backward Splitting
• Convergence rates with inexact non-expansive operators
• Convex analysis and monotone operator theory in Hilbert spaces
• Dual constrained TV-based regularization on graphs
• scientific article; zbMATH DE number 477581 (Why is no real title available?)
• scientific article; zbMATH DE number 3441150 (Why is no real title available?)
• Metric selection in fast dual forward-backward splitting
• Monotone (nonlinear) operators in Hilbert space
• Non-local regularization of inverse problems
• NON-STRICTLY CONVEX MINIMIZATION OVER THE FIXED POINT SET OF AN ASYMPTOTICALLY SHRINKING NONEXPANSIVE MAPPING
• On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision
• Partial inverse of a monotone operator
• Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators
• Proximal quasi-Newton methods for nondifferentiable convex optimization
• Proximité et dualité dans un espace hilbertien
• Quasi-Newton Methods and their Application to Function Minimisation
• Quelques propriétés des opérateurs angle-bornes et n-cycliquement monotones
• Signal Recovery by Proximal Forward-Backward Splitting
• Solving monotone inclusions via compositions of nonexpansive averaged operators
• Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping
• Structured variable selection with sparsity-inducing norms
• Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function
• Variable metric forward-backward splitting with applications to monotone inclusions in duality
• Variable Metric Method for Minimization

Cited in

(23)

• Forward-backward-half forward dynamical systems for monotone inclusion problems with application to v-GNE
• Preconditioned Douglas-Rachford type primal-dual method for solving composite monotone inclusion problems with applications
• An inertial semi-forward-reflected-backward splitting and its application
• A proximal interior point algorithm with applications to image processing
• A note on the forward-Douglas-Rachford splitting for monotone inclusion and convex optimization
• An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization
• Convergence analysis of an inexact three-operator splitting algorithm
• Generalized forward-backward splitting with penalization for monotone inclusion problems
• ADMM for monotone operators: convergence analysis and rates
• Preconditioned three-operator splitting algorithm with applications to image restoration
• A generalized forward-backward splitting
• Parameter selection and preconditioning for a graph form solver
• Cut pursuit: fast algorithms to learn piecewise constant functions on general weighted graphs
• Parallel Normal S-Iteration Methods with Applications to Optimization Problems
• Proximal activation of smooth functions in splitting algorithms for convex image recovery
• Support-Graph Preconditioners
• Convergence of an Inertial Shadow Douglas-Rachford Splitting Algorithm for Monotone Inclusions
• Preconditioned Algorithm for Difference of Convex Functions with Applications to Graph Ginzburg–Landau Model
• An accelerated forward-backward-half forward splitting algorithm for monotone inclusion with applications to image restoration
• Incorporating history and deviations in forward-backward splitting
• The geometry of monotone operator splitting methods
• A modification of the forward-backward splitting method for monotone inclusions
• Variational models for signal processing with graph neural networks

This page was built for publication: Preconditioning of a generalized forward-backward splitting and application to optimization on graphs

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