Proximal operator

Template:Short description In mathematical optimization, the proximal operator is an operator associated with a proper, lower semi-continuous convex function $f$ from a Hilbert space $𝒳$ to $[-\mathrm{\infty },+\mathrm{\infty }]$, and is defined by:

${\mathrm{prox}}_f(v)=\arg \underset{x\in 𝒳}{\min }(f(x)+\frac{1}{2}\Vert x-v{\Vert }_{𝒳}^2).$

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 $\text{prox}$ of a proper, lower semi-continuous convex function $f$ enjoys several useful properties for optimization.

• Fixed points of ${\text{prox}}_f$ are minimizers of $f$: $\{x\in 𝒳|{\text{prox}}_{f}x=x\}=\arg \min f$.
• Global convergence to a minimizer is defined as follows: If $\arg \min f\ne \varnothing$, then for any initial point $x_0\in 𝒳$, the recursion $(\mathrm{\forall }n\in \mathbb{N})x_{n+1}={\text{prox}}_f{x}_n$ yields convergence $x_n\to x\in \arg \min f$ as $n\to +\mathrm{\infty }$. This convergence may be weak if $𝒳$ is infinite dimensional.
• The proximal operator can be seen as a generalization of the projection operator. Indeed, in the specific case where $f$ is the 0-$\mathrm{\infty }$ characteristic function ${\iota }_C$ of a nonempty, closed, convex set $C$ we have that

$\begin{array}{cc}{\mathrm{prox}}_{{\iota }_C}(x)& =\underset{y}{\mathrm{argmin}}\{\begin{array}{cc}\frac{1}{2}{\Vert x-y\Vert }_2^2& \text{if }y\in C\\ +\mathrm{\infty }& \text{if }y\notin C\end{array}\\ & =\underset{y\in C}{\mathrm{argmin}}\frac{1}{2}{\Vert x-y\Vert }_2^2\end{array}$

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

• A function is firmly non-expansive if $(\mathrm{\forall }(x,y)\in {𝒳}^2)\Vert {\text{prox}}_{f}x-{\text{prox}}_{f}y{\Vert }^2\le ⟨x-y,{\text{prox}}_{f}x-{\text{prox}}_{f}y⟩$.
• The proximal operator of a function is related to the gradient of the Moreau envelope $M_{\lambda f}$ of a function $\lambda f$ by the following identity: $\mathrm{\nabla }{M}_{\lambda f}(x)=\frac{1}{\lambda }(x-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{x}}_{\lambda f}(x))$.

• The proximity operator of $f$ is characterized by inclusion $p={\mathrm{prox}}_f(x)\iff x-p\in \partial f(p)$, where $\partial f$ is the subdifferential of $f$, given by

$\partial f(x)=\{u\in {ℝ}^N\mid \mathrm{\forall }y\in {ℝ}^N,(y-x{)}^{\mathrm{T}}u+f(x)\le f(y)\}$ In particular, If $f$ is differentiable then the above equation reduces to $p={\mathrm{prox}}_f(x)\iff x-p=\mathrm{\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.