A proximal decomposition method for solving convex variational inverse problems

By Patrick L. Combettes, Jean-Christophe Pesquet. 2008

300 citations recorded by the source corpus.

A broad range of inverse problems can be abstracted into the problem of minimizing the sum of several convex functions in a Hilbert space. We propose a proximal decomposition algorithm for solving this problem with an arbitrary number of nonsmooth functions and establish its weak convergence. The algorithm fully decomposes the problem in that it involves each function individually via its own proximity operator. A significant improvement over the methods currently in use in the area of inverse problems is that it is not limited to two nonsmooth functions. Numerical applications to signal and image processing problems are demonstrated.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/5a3d3e9d75aecf2e35f98ab153adcda3459159c9

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

Citations in the corpus

Proximal Splitting Methods in Signal Processing (2009, methodology): “For ins tance, the following parallel algorithm was derived from the Douglas-Rachford algo rithm in [54] (see also [49] for further analysis and connections with Spingarn’s s plitting method [120]).”
This is SPIRAL-TAP: Sparse Poisson Intensity Reconstruction ALgorithms—Theory and Practice (2010, methodology): “Finally, the approaches in [38] and [39] applied proximal functions to solve more general constrained convex minimization problems.”
Tensor completion and low-n-rank tensor recovery via convex optimization (2011, background): “It was recently extended in [14] for the minimization of a sum over multiple functions in 0(H), based on a product space formulation.”
A Universal Primal-Dual Convex Optimization Framework (2015, methodology): “The efficiency guarantees of these methods mainly depend on three properties of f : Lipschitz gradient, strong convexity, and the tractability of its proximal operator.”
NESTA: A Fast and Accurate First-Order Method for Sparse Recovery (2009, methodology): “Known methods include interior point methods ( 1-magic) [10], proximalsubgradient methods [5, 19], split Bregman [35], and the very recently introduced RecPF9 [59], which operates in the special case of partial Fourier measurements.”
Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle-Pock algorithm (2011, methodology): “For large-scale systems there has been some resurgence of first-order methods [15], [16], [17], [18], [19], [20] and recently there has been applications of first-order methods specifically for optimization-based image reconstruction in CT [20], [21], [22].”
Convex Optimization for Big Data: Scalable, randomized, and parallel algorithms for big data analytics (2014, methodology): “Algorithm 8 Decomposition algorithm (aka, consensus ADMM) [30] to solve (18); γ > 0, x 0 i = 0 for i = 1 , . . . , n .”
Asynchronous distributed optimization using a randomized alternating direction method of multipliers (2013, methodology): “It is worth noting that in the case of Example 1, the synchronous ADMM described above coincides with the algorithm of [11] and is very close to the so called PPXA algorithm introduced in [12].”
Bayesian computation: a perspective on the current state, and sampling backwards and forwards (2015, methodology): “…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 the parallel primal-dual algorithm (Combettes and Pesquet 2012).”
A Generalized Forward-Backward Splitting (2011, methodology): “If we set B ≡ 0 , the update of the auxiliary variables in (2.1) becomes so that ( z i,k ) i given by (2.2) follow the iterations of the relaxed Douglas-Rachford algorithm on the product space H n for solving 0 ∈ i A i x [24, 71].”
A Fast Alternating Direction Method for TVL1-L2 Signal Reconstruction From Partial Fourier Data (2010, methodology): “Lately, [24] describes the relationships between the split Bregman method, ALM, and ADM, and [18] discusses a proximal decomposition method for convex variational inverse problems.”