A Generalized Forward-Backward Splitting

By Hugo Raguet, Mohamed-Jalal Fadili, G. Peyr'e. 2011

402 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Mathematical Physics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Mathematical Physics

In Optimization & Training

Citations in the corpus

Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, background): “It has been originally introduced by Raguet et al. (2013), to optimize (33) performing projections over the constraint sets.”
Stochastic Variance Reduction Methods for Saddle-Point Problems (2016, neutral): “Note the difference with [29], which requires each Bi to be monotone with a known resolvent and A to be monotone and single-valued.”
Bayesian computation: a summary of the current state, and samples backwards and forwards (2015, methodology): “Lastly, it is worth mentioning that there are other modern proximal optimisation algorithms that can be massively parallelised, for example the generalised forward backward algorithm (Raguet et al. 2013), the parallel proximal algorithms (Combettes and Pesquet 2008; Pesquet and Pustelnik 2012), and ”
Proximal Splitting Algorithms: A Tour of Recent Advances, with New Twists. (2020, background): “On the other hand, if 5 = 0, we recover the Generalized forward–backward algorithm [93,95].”
Forward-Douglas–Rachford splitting and forward-partial inverse method for solving monotone inclusions (2012, methodology): “. In the case when g ≡ 0, the partial inverse method in [44] solves Problem 6.8 with some applications to convex programming. In the general setting, Problem 6.8 can be solved by methods developed in [11, 18, 24] but without exploiting the structure of the problem. Indeed, in the algorithms presente”
Bayesian computation: a perspective on the current state, and sampling backwards and forwards (2015, methodology): “For example, here we use the state-of-the-art ADMM algorithm SALSA (Afonso et al. 2011) implemented with g 1 ( θ ) = (cid:107) y − H θ 22 / 2 σ 2 , g 2 ( u ) = α Raguet et al. 2013)).”
An Inertial Forward-Backward Algorithm for Monotone Inclusions (2014, neutral): “It has been proposed and further improved in the context of sparse signal recovery [15,17], image processing [45], and machine learning [19] applications.”
A Dynamical System Associated with the Fixed Points Set of a Nonexpansive Operator (2014, methodology): “esented here. The same can be done for other iterative schemes which have their origins in the discrete Krasnosel’ski˘ı–Mann algorithm, like are the generalized forwardbackward splitting algorithm in [20] and the forward-Douglas-Rachford splitting algorithm in [13]. 4 An alternative approach relying”
The Cosparse Analysis Model and Algorithms (2011, neutral): “To give just an example, [44] proposes a general form of forward-backward splitting that can be exploited to deal with such problems.”
Sparse Modeling for Image and Vision Processing (2014, methodology): “Following this insight, Ramirez et al. [2009] have shown that promoting incoherent dictionaries may lead to better generalization properties.”
Stein Unbiased GrAdient estimator of the Risk (SUGAR) for Multiple Parameter Selection (2014, methodology): “4 Application to Generalized Forward Backward Splitting The Generalized Forward Backward (GFB) splitting [50] allows one to find one element belonging to the set x(y, θ) solution of the structured convex optimization problem”