Proximal Operators¶

Definition¶

Let $f$ be a proper convex function mapping the normed space $X$ to the extended real number line $(-\infty, +\infty]$ . The proximal operators of the functional $f$ is mapping from $X\mapsto X$ . It is denoted as $\mathrm{prox}_\tau[f](x)$ with $x\in X$ and defined by

$\mathrm{prox}_\tau[f](x) = \arg\;\min_{y\in Y}\;f(y)+\frac{1}{2\tau} \|x-y\|_2^2$

The shorter notation $\mathrm{prox}_{\tau\,f}(x)$ ) is also common.

Properties¶

Some properties which are useful to create or compose proximal operators:

Separable sum

If $f$ is separable across variables, i.e. $f(x,y)=g(x)+h(y)$ , then

$\mathrm{prox}_\tau[f](x, y) = (\mathrm{prox}_\tau[g](x), \mathrm{prox}_\tau[h](y))$

Post-composition

If $g(x)=\alpha f(x)+a$ with $\alpha > 0$ , then

$\mathrm{prox}_\tau[g](x) = \mathrm{prox}_{\alpha\tau}[f](x)$

Pre-composition

If $g(x)=f(\beta x+b)$ with $\beta\ne 0$ , then

$\mathrm{prox}_\tau[g](x) = \frac{1}{\beta} (\mathrm{prox}_{\beta^2\tau}[f](\beta x+b)-b)$

Moreau decomposition

This is also know as the Moreau identity

$x = \mathrm{prox}_\tau[f](x) + \frac{1}{\tau}\,\mathrm{prox}_{1/\tau}[f^*] (\frac{x}{\tau})$

where $f^*$ is the convex conjugate of $f$ .

Convec conjugate

The convex conjugate of $f$ is defined as

$f^*(y) = \sup_{x\in X} \langle y,x\rangle - f(x)$

where $\langle\cdot,\cdot\rangle$ denotes inner product. For more on convex conjugate and convex analysis see [Roc1970] or Wikipedia.

For more details on proximal operators including how to evaluate the proximal operator of a variety of functions see [PB2014].

Indicator function¶

Indicator functions are typically used to incorporate constraints. The indicator function for a given set $S$ is defined as

$\mathrm{ind}_{S}(x) =\begin{cases} 0 & x \in S \\ \infty & x\ \notin S \end{cases}$

Special indicator functions

Indicator for a box centered at origin and with width $2 a$ :

$\mathrm{ind}_{\mathrm{box}(a)}(x) = \begin{cases} 0 & \|x\|_\infty \le a\\ \infty & \|x\|_\infty > a \end{cases}$

where $\|\cdot\|_\infty$ denotes the maximum-norm.