# Proximal operator

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Proximal_operator
> Markdown URL: https://mediated.wiki/source/Proximal_operator.md
> Source: https://en.wikipedia.org/wiki/Proximal_operator
> Source revision: 1303737679
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Function in mathematical optimization}}
In [mathematical optimization](/source/mathematical_optimization), the '''proximal''' operator is an [operator](/source/Operator_(mathematics)) associated with a proper,<ref group="note">An [(extended) real-valued](/source/Extended_real_number_line) function ''f'' on a [Hilbert space](/source/Hilbert_space) is said to be ''proper'' if it is not identically equal to <math>+\infty</math>, and <math>-\infty</math> is not in its image.</ref> [lower semi-continuous](/source/Semi-continuity) [convex function](/source/convex_function) <math>f</math> from a [Hilbert space](/source/Hilbert_space) <math>\mathcal{X}</math>
to <math>[-\infty,+\infty]</math>, and is defined by:<ref>{{cite journal|url=https://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf |title=Proximal Algorithms |author=Neal Parikh and Stephen Boyd |journal= Foundations and Trends in Optimization |volume=1 |issue=3 |year=2013 |pages=123–231 |access-date=2019-01-29}}</ref>

::<math>\operatorname{prox}_f(v) = \arg \min_{x\in\mathcal{X}} \left(f(x) + \frac 1 2 \|x - v\|_\mathcal{X}^2\right).</math>  
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](/source/Differentiable_function) optimization problems such as [total variation denoising](/source/total_variation_denoising).

== Properties ==
The <math>\text{prox}</math> of a proper, lower semi-continuous convex function <math>f</math> enjoys several useful properties for optimization.

* Fixed points of <math>\text{prox}_f</math> are minimizers of <math>f</math>: <math>\{x\in \mathcal{X}\ |\ \text{prox}_fx = x\} = \arg \min f</math>.
* Global convergence to a minimizer is defined as follows: If <math>\arg \min f \neq \varnothing</math>, then for any initial point <math>x_0 \in \mathcal{X}</math>, the recursion <math>(\forall n \in \mathbb{N})\quad x_{n+1} = \text{prox}_f x_n</math> yields convergence <math>x_n \to x \in \arg \min f </math> as <math>n \to +\infty</math>. This convergence may be weak if <math>\mathcal{X}</math> is infinite dimensional.<ref>{{Cite book |last=Bauschke |first=Heinz H. |title=Convex Analysis and Monotone Operator Theory in Hilbert Spaces |last2=Combettes |first2=Patrick L. |publisher=Springer |year=2017 |isbn=978-3-319-48310-8 |series=CMS Books in Mathematics |location=New York |doi=10.1007/978-3-319-48311-5}}</ref>
* The proximal operator can be seen as a generalization of the [projection operator](/source/Projection_(linear_algebra)). Indeed, in the specific case where <math>f</math> is the [0-<math>\infty</math> characteristic function](/source/Characteristic_function_(convex_analysis))  <math>\iota_C</math> of a nonempty, closed, convex set <math>C</math> we have that
: <math> 
\begin{align}
\operatorname{prox}_{\iota_C}(x)
&= \operatorname{argmin}\limits_y
\begin{cases}
\frac{1}{2} \left\| x-y \right\|_2^2 &  \text{if } y \in C \\
+ \infty                             &  \text{if } y \notin C 
\end{cases} \\
&=\operatorname{argmin}\limits_{y \in C} \frac{1}{2} \left\| x-y \right\|_2^2 
\end{align}
</math>
: showing that the proximity operator is indeed a generalisation of the projection operator.

* A function is [firmly non-expansive](/source/Contraction_mapping) if  <math>(\forall (x,y) \in \mathcal{X}^2) \quad \|\text{prox}_fx - \text{prox}_fy\|^2 \leq \langle x-y\ , \text{prox}_fx - \text{prox}_fy\rangle</math>.
* The proximal operator of a function is related to the gradient of the [Moreau envelope](/source/Moreau_envelope) <math>M_{\lambda f}</math> of a function <math>\lambda f</math> by the following identity: <math>\nabla M_{\lambda f}(x) = \frac{1}{\lambda} (x - \mathrm{prox}_{\lambda f}(x))</math>.
* The proximity operator of <math>f</math> is characterized by inclusion <math> p=\operatorname{prox}_f(x) \Leftrightarrow x-p \in \partial f(p)
</math>, where <math> \partial f </math> is the [subdifferential](/source/subdifferential) of <math>f</math>, given by
: <math>
 \partial f(x) = \{ u \in \mathbb{R}^N \mid \forall y \in \mathbb{R}^N, (y-x)^\mathrm{T}u+f(x) \leq f(y)\}
</math> In particular, If <math>f</math> is differentiable then the above equation reduces to <math> p=\operatorname{prox}_f(x) \Leftrightarrow x-p = \nabla f(p)
</math>.

== Notes ==
{{reflist|group=note}}

==References==
{{Reflist}}

== See also ==
* [Proximal gradient method](/source/Proximal_gradient_method)

==External links==
* The [http://proximity-operator.net/ Proximity Operator repository]: a collection of proximity operators implemented in [Matlab](/source/Matlab) and [Python](/source/Python_(programming_language)).
* [https://github.com/kul-forbes/ProximalOperators.jl ProximalOperators.jl]: a [Julia](/source/Julia_(programming_language)) package implementing proximal operators.
* [https://github.com/odlgroup/odl ODL]: a Python library for [inverse problems](/source/inverse_problems) that utilizes proximal operators.

Category:Mathematical optimization

---
Adapted from the Wikipedia article [Proximal operator](https://en.wikipedia.org/wiki/Proximal_operator) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Proximal_operator?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.