Proximal operator explained

f from a Hilbert space l{X} to [ -inf ty, +inf ty] , and is defined by: ^[2] \operatorname{prox} _{f(v)} = \arg min _{x\inl{X} } \left(f(x) + \frac 1 2 \|x - v\|_\mathcal^2\right). For any function in this class, the minimizer of the right-hand side above is unique, hence making the proximal operator well-defined. The proximal operator is used in proximal gradient methods, which is frequently used in optimization algorithms associated with non-differentiable optimization problems such as total variation denoising.

Properties

The

prox of a proper, lower semi-continuous convex function f enjoys several useful properties for optimization.

• Fixed points of

prox _{f} are minimizers of f : \{x\in l{X} | prox _{fx} = x\} = \arg min f .

• Global convergence to a minimizer is defined as follows: If

\arg min f ≠ \varnothing , then for any initial point x _{0} \in l{X} , the recursion (\forall n \in N ) x _{n+1} = prox _{f} x _{n} yields convergence x _{n} \to x \in \arg min f as n \to +inf ty . This convergence may be weak if l{X} is infinite dimensional.^[3]

• The proximal operator can be seen as a generalization of the projection operator. Indeed, in the specific case where

f is the 0-inf ty indicator function \iota _{C} of a nonempty, closed, convex set C we have that\begin{align} \operatorname{prox} _{\iota _{C}} (x) & = \operatorname{argmin}\limits _{y \begin{cases} (1)/(2)} \left\| x - y \right\| ^{2} _{2} & if y \in C \\ + inf ty & if y \notin C \end{cases} \\ & = \operatorname{argmin}\limits _{y} (1)/(2) \left\| x - y \right\| ^{2} _{2} \end{align}

showing that the proximity operator is indeed a generalisation of the projection operator.

• A function is firmly non-expansive if

(\forall (x,y) \in l{X} ^{2)} \| prox _{fx} - prox ^{2} _{fy\|} \leq \langle x - y | prox _{fx} - prox _{fy\rangle} .M _{λ} of a function λ f by the following identity: \nabla M _{λ} (x) = (1)/(λ) (x - prox _{λ} (x)) .

• The proximity operator of

f is characterized by inclusion p = \operatorname{prox} _{f(x)} \Leftrightarrow x - p \in \partial f(p) , where \partial f is the subdifferential of f , given by\partial f(x) = \{ u \in R ^{N} \mid \forall y \in R ^{N,} (y - x) ^{Tu+f(x)} \leq f(y)\} In particular, If f is differentiable then the above equation reduces to p = \operatorname{prox} _{f(x)} \Leftrightarrow x - p = \nabla f(p) .

See also

• Proximal gradient method

External links

• The Proximity Operator repository: a collection of proximity operators implemented in Matlab and Python.
• ProximalOperators.jl: a Julia package implementing proximal operators.
• ODL: a Python library for inverse problems that utilizes proximal operators.

Notes and References

1. An (extended) real-valued function f on a Hilbert space is said to be proper if it is not identically equal to +inf ty , and -inf ty is not in its image.
2. Proximal Algorithms . Neal Parikh and Stephen Boyd . Foundations and Trends in Optimization . 1 . 3 . 2013 . 123–231 . 2019-01-29.
3. Book: Bauschke, Heinz H. . Convex Analysis and Monotone Operator Theory in Hilbert Spaces . Combettes . Patrick L. . Springer . 2017 . 978-3-319-48310-8 . CMS Books in Mathematics . New York . 10.1007/978-3-319-48311-5.