Proximal Operators


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.


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))


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

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


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

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

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