Generalized Forward-Backward Splitting

Abstract

This paper introduces the generalized forward-backward splitting algorithm for minimizing convex functions of the form $F+{\sum }_{i=1}^n{G}_i$, where $F$ has a Lipschitz-continuous gradient and the $G_i$'s are simple in the sense that their Moreau proximity operators are easy to compute. While the forward-backward algorithm cannot deal with more than $n=1$ non-smooth function, our method generalizes it to the case of arbitrary $n$. Our method makes an explicit use of the regularity of $F$ in the forward step, and the proximity operators of the $G_i$'s are applied in parallel in the backward step. This allows the generalized forward backward to efficiently address an important class of convex problems. We prove its convergence in infinite dimension, and its robustness to errors on the computation of the proximity operators and of the gradient of $F$. Examples on inverse problems in imaging demonstrate the advantage of the proposed methods in comparison to other splitting algorithms.

24 pages, 4 figures

References in corpus (1)

• A proximal iteration for deconvolving Poisson noisy images using sparse representations

Cited by in corpus (77)

• An inertial forward-backward algorithm for monotone inclusions
• Estimation of Simultaneously Sparse and Low Rank Matrices
• A quasi-Newton proximal splitting method
• Fixed Point Strategies in Data Science
• Compressive Deconvolution in Medical Ultrasound Imaging
• Improved Sparse Low-Rank Matrix Estimation
• Non-convex regularization in remote sensing
• PySAP: Python Sparse Data Analysis Package for Multidisciplinary Image Processing
• Proximal-Proximal-Gradient Method
• Projected Nesterov's Proximal-Gradient Algorithm for Sparse Signal Reconstruction with a Convex Constraint
• NMF with Sparse Regularizations in Transformed Domains
• Super-resolution method using sparse regularization for point-spread function recovery
• An inertial three-operator splitting algorithm with applications to image inpainting
• Euclid: Nonparametric point spread function field recovery through interpolation on a graph Laplacian
• Graphical Inference in Linear-Gaussian State-Space Models
• Local and Global Convergence of a General Inertial Proximal Splitting Scheme
• Non-parametric PSF estimation from celestial transit solar images using blind deconvolution
• Bayesian computation: a perspective on the current state, and sampling backwards and forwards
• Fast Multi-grid Methods for Minimizing Curvature Energy
• Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization
• Two-pixel polarimetric camera by compressive sensing
• Variational Model-Based Reconstruction Techniques for Multi-Patch Data in Magnetic Particle Imaging
• Social Network Fusion and Mining: A Survey
• The Application of Preconditioned Alternating Direction Method of Multipliers in Depth from Focal Stack
• Stochastic Quasi-Fejér Block-Coordinate Fixed Point Iterations with Random Sweeping
• Geometry of First-Order Methods and Adaptive Acceleration
• A Class of Randomized Primal-Dual Algorithms for Distributed Optimization
• A Scale Invariant Approach for Sparse Signal Recovery
• Adaptive Three Operator Splitting
• String-Averaging Incremental Subgradients for Constrained Convex Optimization with Applications to Reconstruction of Tomographic Images
• A first-order splitting method for solving a large-scale composite convex optimization problem
• A splitting algorithm for dual monotone inclusions involving cocoercive operators
• Hemodynamic Deconvolution Demystified: Sparsity-Driven Regularization at Work
• Link Prediction in Graphs with Autoregressive Features
• Variational Graph Methods for Efficient Point Cloud Sparsification
• Linear convergence of the generalized PPA and several splitting methods for the composite inclusion problem
• A new splitting method for solving composite monotone inclusions involving parallel-sum operators
• Local and Global Convergence of an Inertial Version of Forward-Backward Splitting
• Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
• Convergence Rates with Inexact Non-expansive Operators
• Compressive lensless endoscopy with partial speckle scanning
• A stochastic inertial forward-backward splitting algorithm for multivariate monotone inclusions
• Uniqueness of DRS as the 2 Operator Resolvent-Splitting and Impossibility of 3 Operator Resolvent-Splitting
• An Algorithmic Framework of Variable Metric Over-Relaxed Hybrid Proximal Extra-Gradient Method
• Accelerated Reconstruction of Perfusion-Weighted MRI Enforcing Jointly Local and Nonlocal Spatio-temporal Constraints
• Three Operator Splitting with Subgradients, Stochastic Gradients, and Adaptive Learning Rates
• On the convergence rate of the three operator splitting scheme
• A Sequential Constraint Method for Solving Variational Inequality over the Intersection of Fixed Point Sets
• An Inertial Parallel and Asynchronous Fixed-Point Iteration for Convex Optimization
• A Note on the Forward-Douglas--Rachford Splitting for Monotone Inclusion and Convex Optimization
• Three Operator Splitting with a Nonconvex Loss Function
• A general approach to distributed operator splitting
• A randomized intertial primal-dual fixed point algorithm for monotone inclusions
• Fast convergence of generalized forward-backward algorithms for structured monotone inclusions
• On the metric resolvent: nonexpansiveness, convergence rates and applications
• Iteration-Complexity of a Generalized Forward Backward Splitting Algorithm
• An adaptive splitting algorithm for the sum of three operators
• An Overview of Lead and Accompaniment Separation in Music
• Compositions and Convex Combinations of Averaged Nonexpansive Operators
• An outer reflected forward-backward splitting algorithm for solving monotone inclusions
• Solving Coupled Composite Monotone Inclusions by Successive Fejér Approximations of Their Kuhn-Tucker Set
• Robust image reconstruction from multi-view measurements
• Forward--partial inverse--forward splitting for solving monotone inclusions
• Forward-Douglas-Rachford splitting and forward-partial inverse method for solving monotone inclusions
• Cocoercivity, Smoothness and Bias in Variance-Reduced Stochastic Gradient Methods
• Convergence analysis of an inexact inertial Krasnoselskii-Mann algorithm with applications
• Convergence analysis of a relaxed inertial alternating minimization algorithm with applications
• GFB-MRF: A parallel spatial and Bloch manifold regularized iterative reconstruction method for MR Fingerprinting
• A primal-dual splitting algorithm for monotone inclusions with applications
• Graph Prediction in a Low-Rank and Autoregressive Setting
• Projection and contraction methods with double inertial steps for variational inclusion problems on Hilbert spaces
• A Stochastic Variance Reduced Primal Dual Fixed Point Method For Linearly Constrained Separable Optimization
• Activity Identification and Local Linear Convergence of Douglas--Rachford/ADMM under Partial Smoothness
• Inertial Three-Operator Splitting Method and Applications
• Automatic discovery of discriminative parts as a quadratic assignment problem
• Handling convexity-like constraints in variational problems
• Adapted Basis for Non-Local Reconstruction of Missing Spectrum