Source-linked AI summary
A Proximal Decomposition Method for Solving Convex Variational Inverse Problems
Patrick L. Combettes, Jean-Christophe Pesquet
TL;DR
The paper addresses inverse problems expressed as sums of several convex functions, especially cases with three or more potentials and multiple nonsmooth terms. It proposes a product-space proximal decomposition algorithm using each function's proximity operator separately, proves convergence, and demonstrates efficient signal and image recovery applications.
Problem
Existing inverse-problem methods are restricted to at most two nonsmooth potentials, excluding formulations with three or more potentials and multiple nonsmooth terms.
Method
The paper reformulates the problem in a product space and applies a decomposition algorithm that uses each function separately through its own proximity operator.
Results
The method's signal and image processing applications show that complex nonsmooth variational inverse problems beyond reviewed methods can be decomposed and solved efficiently.
Takeaways & Limitations
The algorithm handles an arbitrary number of nonsmooth potentials and activates their proximity operators in parallel at each iteration.
Takeaways & Limitations
One phase-retrieval experiment models measurement uncertainty by introducing a 5% perturbation on each phase component and smoothing a hard potential.
Abstract
from arXiv · showhide
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 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.
1 Introduction
The paper studies inverse problems formulated as minimizing sums of proper lower semicontinuous convex functions in a real Hilbert space. It targets cases with at least three potentials and multiple nonsmooth terms, which existing approaches do not cover.
- The problem is to minimize a sum of proper lower semicontinuous convex functions over a real Hilbert space.
- Many inverse problems, including denoising, deconvolution, image recovery, restoration, sparse reconstruction, and tomography, fit this decomposed optimization framework.
- When convex-set constraints are inaccurate, the feasibility set may be empty, motivating approximate solutions through weighted squared distance functions.
- Existing two-function approaches often require all but one function to be Lipschitz-differentiable or require an implementable proximity operator for the second function.
- The proposed product-space reformulation handles three or more potentials, including multiple nonsmooth functions, by using each function's proximity operator separately.
- The paper introduces the decomposition method, proves weak convergence, and demonstrates efficient solutions for complex nonsmooth signal and image problems.
2 Notation and background
This section establishes the Hilbert-space convex-analysis notation and develops proximity-operator results used by the algorithm. It supplies general identities and closed-form constructions for projections, distance-based functions, and quadratic compositions.
- Convex analysis: The analysis uses real Hilbert spaces and proper lower semicontinuous convex functions, with standard notions including domains, conjugates, subdifferentials, and relative interiors.
- Distance-based functions: For functions formed by composing an even convex scalar function with a distance to a convex set, the conjugate decomposes into a support function and a scalar conjugate applied to the norm.
- Proximity operators: The proximity operator maps each point to the unique minimizer of a function plus a squared-distance penalty, equivalently (Id + ∂f)^-1.
- Examples of proximity operators: Closed-form or computable formulas are provided for quadratic compositions with linear operators and powers of distance functions, including αd_C^p and the p = 3/2 case.
- Examples of proximity operators: The proximity operator of a distance-based function can be decomposed using the proximity operator of the conjugate scalar function and projection onto the convex set.
3 Algorithm and convergence
Algorithm 3.1 decomposes convex minimization in a product Hilbert space, using each function through its own proximity operator. Under stated coercivity, qualification, relaxation, and error conditions, its iterates converge weakly to a minimizer.
- 3.1 Algorithm: The algorithm uses each function separately through its own proximity operator, allowing decomposition of problems with multiple nonsmooth functions.The product-space reformulation captures formulations with three or more potentials without requiring any function to be differentiable.
- 3.1 Algorithm: At every iteration, proximal and auxiliary vectors can be computed simultaneously, while summable errors are tolerated in proximity-operator evaluations.The parallel structure applies across all functions indexed by i = 1, . . . , m.
- 3.2 The Douglas-Rachford algorithm for minimization problems: For two convex functions, the Douglas–Rachford framework converges weakly to a fixed point whose proximity image is a minimizer of their sum.The minimizer is obtained indirectly as proxγf2 y, where y is the weak limit of the generated sequence.
- 3.2 The Douglas-Rachford algorithm for minimization problems: Under the proposition’s assumptions, constrained Douglas–Rachford iterates converge weakly to a point in the set of minimizers over the constraint subspace.The result uses projection onto a closed vector subspace and a coercivity condition on the constrained objective.
- 3.3 Convergence of Algorithm 3.1: When m = 2, Algorithm 3.1 differs from standard Douglas–Rachford iteration but directly produces a sequence converging weakly to a minimizer.The paper presents this direct minimizer convergence as an advantage of the proposed formulation in the two-function case.
4 Applications to signal and image processing
The applications demonstrate Algorithm 3.1 on image restoration problems using multiple convex constraints and potentials, including hybrid sparsity and total-variation models. The experiments report sharper restorations and improved errors when the combined potentials are used.
- Experimental setup: Algorithm 3.1 is implemented in three signal and image-processing experiments with equal weights, λn = 1.5, exact proximity operators, and sufficiently many iterations.The proximity operators are computable in closed form, so implementation errors are set to zero.
- Experiment 1: Experiment 1 restores a blurred, noisy 512 × 512 image with a relative quadratic error of −23.25 dB versus the original.The degradation uses a 15 × 15 uniform blur kernel and zero-mean white Gaussian noise; the restoration is shown after 300 iterations with γ = 1/4.
- Experiment 2: Experiment 2 models restoration in a tight-frame coefficient space using least-squares fidelity, an ℓ1 sparsity potential, and discrete total variation.The total-variation term is split into four terms because its composition with the synthesis operator lacks an explicit proximity operator.
- Experiment 2: 350 iterations of the combined Experiment 2 model achieve a relative mean-square error of −14.82 dB, compared with −14.06 dB without total variation and −13.70 dB without ℓ1.Removing total variation produces small visual artifacts, while removing ℓ1 yields less-sharp details.
5 Concluding remarks
The paper proposes a proximal method for inverse problems formulated as minimizing sums of lower semicontinuous convex potentials. Unlike existing methods limited to two nonsmooth potentials, it handles arbitrarily many, uses each potential’s proximity operator in parallel, and is demonstrated on signal and image recovery.
- The proposed method solves inverse problems decomposed into minimizing a sum of lower semicontinuous convex potentials.
- Unlike methods restricted to at most two nonsmooth potentials, the algorithm handles an arbitrary number of them.This expands the range of scenarios and increases numerical implementation flexibility.
- Each potential is incorporated through its own proximity operator, which the algorithm activates in parallel at every iteration.
- Applications in signal and image recovery demonstrate the method’s versatility across multiple decomposition schemes.One application mixes total variation with other nonsmooth potentials.