Proximal operator

In mathematical optimization, the proximal operator is an operator associated with a proper,^{[note 1]} lower semi-continuous convex function ${\displaystyle f}$ from a Hilbert space ${\displaystyle {\mathcal {X}}}$ to ${\displaystyle [-\infty ,+\infty ]}$, and is defined by: ^[1]

${\displaystyle \operatorname {prox} _{f}(v)=\arg \min _{x\in {\mathcal {X}}}\left(f(x)+{\frac {1}{2}}\|x-v\|_{\mathcal {X}}^{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 ${\displaystyle {\text{prox}}}$ of a proper, lower semi-continuous convex function ${\displaystyle f}$ enjoys several useful properties for optimization.

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

${\displaystyle {\begin{aligned}\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{aligned}}}$

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

• A function is firmly non-expansive if ${\displaystyle (\forall (x,y)\in {\mathcal {X}}^{2})\quad \|{\text{prox}}_{f}x-{\text{prox}}_{f}y\|^{2}\leq \langle x-y\ |\ {\text{prox}}_{f}x-{\text{prox}}_{f}y\rangle }$.
• The proximal operator of a function is related to the gradient of the Moreau envelope ${\displaystyle M_{\lambda f}}$ of a function ${\displaystyle \lambda f}$ by the following identity: ${\displaystyle \nabla M_{\lambda f}(x)={\frac {1}{\lambda }}(x-\mathrm {prox} _{\lambda f}(x))}$.

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

${\displaystyle \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)\}}$ In particular, If ${\displaystyle f}$ is differentiable then the above equation reduces to ${\displaystyle p=\operatorname {prox} _{f}(x)\Leftrightarrow x-p=\nabla f(p)}$.

Notes

References