Source-linked AI summary
Proximal Splitting Methods in Signal Processing
Patrick L. Combettes, Jean-Christophe Pesquet
TL;DR
Signal-processing optimization often involves convex but nondifferentiable functions, limiting conventional smooth methods. The paper reviews proximity operators and splitting algorithms, showing that they unify established methods and support signal and image-processing applications. It also identifies convergence limitations for some variants.
Problem
Many signal processing problems involve convex optimization with nondifferentiable functions, which rules out conventional smooth optimization techniques.
Method
The paper reviews proximity operators and proximal splitting algorithms that process the component functions individually.
Results
Proximal algorithms capture several apparently unrelated methods, including iterative thresholding, projected Landweber, and alternating-direction method of multipliers, within a unifying framework.
Takeaways & Limitations
These methods apply to signal and image processing problems ranging from restoration and reconstruction to synthesis and design, including nondifferentiable objectives.
Takeaways & Limitations
Linear convergence of forward-backward iterates generally fails and requires additional assumptions, while some objective-value-rate variants no longer guarantee iterate convergence.
Abstract
from arXiv · showhide
The proximity operator of a convex function is a natural extension of the notion of a projection operator onto a convex set. This tool, which plays a central role in the analysis and the numerical solution of convex optimization problems, has recently been introduced in the arena of signal processing, where it has become increasingly important. In this paper, we review the basic properties of proximity operators which are relevant to signal processing and present optimization methods based on these operators. These proximal splitting methods are shown to capture and extend several well-known algorithms in a unifying framework. Applications of proximal methods in signal recovery and synthesis are discussed.
1 Introduction
The paper addresses convex optimization problems in signal processing where some component functions are nondifferentiable. It develops proximal splitting methods that handle functions individually and unify several established algorithms.
- Many signal processing problems can be formulated as convex optimization problems involving multiple convex functions.
- Nondifferentiable component functions rule out conventional smooth optimization techniques.
- Proximal splitting methods use each function individually through its proximity operator to produce easily implementable algorithms.
- The paper reviews proximity operators and proximal algorithms for signal and image processing while restricting the analysis to finite-dimensional spaces.
- Iterative thresholding, projected Landweber, projected gradient, alternating projections, alternating-direction multipliers, and alternating split Bregman are presented as special instances of proximal algorithms.
2 From projection to proximity operators
Proximity operators extend convex projections from indicator functions of sets to arbitrary lower semicontinuous convex functions. Their properties support iterative optimization methods and provide a denoising interpretation for signal processing.
- Projection methods activate individual convex constraints through projection operators, but more general operators are needed beyond convex feasibility problems.
- A proximity operator replaces a set indicator function with an arbitrary function in Γ0(RN) and returns the unique minimizer of a regularized problem.
- For differentiable functions, the proximity condition reduces to x − p = ∇f(p).
- Proximity operators are firmly nonexpansive, and their fixed points are precisely the minimizers of the associated function.
- In denoising, the squared-distance term provides data fidelity while f models prior knowledge about the signal.
3 Forward-backward splitting
Forward-backward splitting solves problems with one smooth convex function and one potentially nonsmooth function by combining a gradient step with a proximity step. Its convergence guarantees unify several established signal-processing algorithms, although linear convergence of iterates generally requires additional assumptions.
- Algorithm and assumptions: The forward-backward algorithm addresses two-function problems where f2 is convex differentiable with β-Lipschitz continuous gradient, while f1 may be nonsmooth.It combines an explicit gradient step using f2 with an implicit proximity step using f1.
- Variants: Relaxed forward-backward variants retain convergence with γn ∈ [ε, 2/β − ε] and λn ∈ [ε, 1], while another variant permits λn ∈ [ε, 3/2 − ε].The latter uses constant step-sizes and larger relaxation parameters.
- Convergence: Every sequence generated by the forward-backward algorithm converges to a solution to Problem 3.1.
- Acceleration and limitations: Linear convergence of forward-backward iterates can fail even in simple settings and requires additional assumptions on the problem.
- Special cases: Projected gradient, projected Landweber, backward-backward, alternating projections, and iterative thresholding arise as special cases of the forward-backward framework.These instances cover applications including denoising, deblurring, computer vision, signal restoration, sparse recovery, and signal synthesis.
4 Douglas-Rachford splitting
Douglas-Rachford splitting solves two-function convex problems by separating the functions into proximal steps, without requiring either function to have a Lipschitz continuous gradient. Under the stated algorithmic conditions, its iterates converge to a solution, but the method may require more computation per iteration than forward-backward splitting.
- Problem and algorithm: Douglas-Rachford splitting addresses two-function convex problems through a two-level condition that motivates its iterative scheme.
- Algorithm: The algorithm alternates proximal updates for the two functions and permits relaxation parameters λ_n in [ε, 2 − ε].
- Convergence: Every sequence generated by the Douglas-Rachford algorithm converges to a solution of the problem.
- Comparison with forward-backward: Unlike forward-backward splitting, Douglas-Rachford does not require a Lipschitz continuous gradient, but it performs two proximal steps per iteration.
- Variants and limitations: The Peaceman-Rachford algorithm is the limiting case with λ_n ≡ 2, and its convergence requires additional assumptions such as strict convexity and real-valuedness of f_2.
5 Dykstra-like splitting
Dykstra-like proximal splitting iteratively computes the proximity operator of a sum by applying the proximity operators of its component functions separately. The method converges to the unique solution of the quadratic-regularized problem and reduces to Dykstra’s projection method for indicator functions.
- Problem setting: The section considers problems with a quadratic term penalizing deviation from a reference signal r, including least-squares variational denoising.
- Motivation: The proximity operator of a sum is usually intractable, motivating an iterative Douglas-Rachford-based decomposition under a minimal feasibility condition.
- Algorithm: The Dykstra-like proximal algorithm alternates prox_g and prox_f updates while maintaining correction variables p_n and q_n.
- Convergence: Every sequence generated by the Dykstra-like proximal algorithm converges to the solution of the problem.
- Special case: When f and g are indicator functions of closed convex sets, the method reduces to Dykstra’s projection method for projecting r onto C ∩ D.
6 Composite problems
Composite proximal methods handle objectives involving a linear transformation by selecting splitting algorithms according to smoothness, matrix, and quadratic-regularization structure. Under their respective assumptions, the forward-backward, Douglas-Rachford, Dykstra-like, and dual methods converge to solutions.
- Problem setting: Composite problems minimize f(x) + g(Lx) under domain compatibility and coercivity conditions that guarantee existence of a solution.
- Forward-backward splitting: When g has a τ-Lipschitz continuous gradient, forward-backward splitting applies because g ◦ L has Lipschitz constant β = τ∥L∥^2.
- Forward-backward splitting: The forward-backward updates use L^⊤∇g(Lx_n), a proximal step for f, and step sizes γ_n ∈ [ε, 2/(τ∥L∥^2) − ε].
- Douglas-Rachford splitting: When L satisfies the stated matrix condition and the relative-interior qualification holds, Douglas-Rachford splitting applies and converges by Proposition 4.3.
- Quadratic regularization: For objectives containing a quadratic data-fitting term, Dykstra-like splitting or dual forward-backward splitting provides solution methods depending on decomposability and qualification conditions.
- Dual method: Under the relative-interior condition, every sequence generated by the dual forward-backward algorithm converges to the solution.
- ADMM: ADMM minimizes the augmented Lagrangian successively over x and y, then performs a proximal maximization step in the multiplier.
7 Problems with m ≥2 functions
The section extends proximal splitting to problems with m ≥ 2 convex functions by using product-space reformulations and parallel algorithms. It gives convergence results and signal-processing applications, including image recovery and composite problems with linear transformations.
- Product-space reformulation: Product-space reformulation converts an m-function problem into an equivalent two-function problem in a larger space.This enables the use of splitting methods developed for two functions.
- Parallel proximal algorithms: PPXA is a parallel proximal algorithm derived from Douglas-Rachford splitting for the reformulated problem.Its iterations use weighted proximity operators and relaxation parameters constrained by ε ≤ λ_n ≤ 2 − ε.
- Convergence: Every sequence generated by Algorithm 7.2 converges to a solution to Problem 7.1.
- Applications: Image recovery can combine a constraint indicator, least-squares data fidelity, frame-coefficient regularization, and decomposed total variation within the multi-function framework.The total-variation terms can be chosen so that their proximity operators have closed-form expressions.
- Dykstra-like methods: Parallel Dykstra-like proximal iterations apply individual proximity operators, aggregate their outputs, and update auxiliary variables.
- Convergence: Every sequence generated by Algorithm 7.6 converges to the solution to Problem 7.5.
8 Conclusion
The paper presents proximal optimization algorithms that use proximity operators and split objectives into simpler functions. These methods apply to diverse signal and image processing problems, including nondifferentiable and hard-constrained objectives.
- Proximal algorithms combine proximity operators with objective splitting into simpler functions handled individually.
- The methods apply to restoration, reconstruction, synthesis, and design problems in signal and image processing.
- They can minimize nondifferentiable objectives arising in sparse approximation, compressed sensing, and hard-constrained problems.
- Approximate proximity operators can serve as subroutines inside error-tolerant proximal splitting algorithms.