Proximity operator

Definition - Properties - Special functions - Affine sets - Extensions

Definition

In the 1960s, Jean Jacques Moreau ([Moreau, 1962]) proposed a useful extension of the notion of projection operator to any arbitrary convex function, leading to the so-called proximity operator. Let $\mathcal{H}$ be a real Hilbert space (e.g., Euclidean space, space of symmetric matrices, etc.), and denote by $\Gamma_0(\mathcal{H})$ the set of lower semi-continuous convex functions from $\mathcal{H}$ to $\left]-\infty,+\infty\right]$.

Let $f \in \Gamma_0(\mathcal{H})$. For every $x \in \mathcal{H}$, the minimization problem $$ \operatorname*{minimize}_{y \in \mathcal{H}}\; f(y) + \frac{1}{2}\|x − y\|^2 $$ admits a unique solution, which is denoted by $\operatorname{prox}_f(x)$.

The operator $\,\operatorname{prox}_f : \mathcal{H} \to \mathcal{H}\,$ thus defined is the proximity operator of $f$.

Proximal calculus revolves around the following important properties. Some of them, arising from [Combettes, 2001] [Combettes and Wajs, 2005] [Combettes and Pesquet, 2007] [Briceño-Arias and Combettes, 2009] [Bauschke and Combettes, 2017], are listed below.

Some properties

$f: x\in\mathcal{H} \to \left]-\infty,+\infty\right]$

$A\in\mathcal{B}(\mathcal{H},\mathcal{K})$, $z\in\mathcal{H}$, $b\in\mathcal{K}$, $\rho\neq0$, $\alpha\ge0$, $\nu>0$, $\varphi\in\Gamma_0(\mathcal{H})$, $\psi\in\Gamma_0(\mathcal{K})$

$\operatorname{prox}_{\gamma f}(x)$

$\gamma > 0$

$\varphi(x) + \alpha \|x\|^2 + \langle z | x \rangle$ $\operatorname{prox}_{\gamma \varphi/(2\alpha\gamma+1)}\left(\dfrac{x-\gamma z}{2\alpha\gamma+1}\right)$
$\varphi\left(\dfrac{x}{\rho}-z\right)$ $\rho z + \rho \operatorname{prox}_{\gamma\varphi/\rho^{2}}\left(\dfrac{x}{\rho} - z\right)$
$\psi(Ax+b)$      with $A A^*=\nu \, {\rm Id}$ $x + \dfrac{1}{\nu} A^*\left( \operatorname{prox}_{\nu\gamma\psi}(Ax+b) - Ax - b \right)$
$\displaystyle{}^\nu\varphi(x) = \operatorname*{inf}_{y\in\mathcal{H}}\; \varphi(y)+\frac{1}{2\nu}\|y-x\|^2$ $\dfrac{1}{\nu+\gamma}\Big(\nu x+\gamma\operatorname{prox}_{(\nu+\gamma)\varphi}(x) \Big)$
$\displaystyle\varphi^*(x) = \sup_{y\in \mathcal{H}}\, \langle x | y \rangle - \varphi(y)$ $x - \gamma \operatorname{prox}_{\varphi/\gamma}\left(\dfrac{x}{\gamma}\right)$

Special functions

$f: x\in\mathcal{H} \to \left]-\infty,+\infty\right]$

$C\subset\mathcal{H}$ is a nonempty closed convex set

$\operatorname{prox}_{\gamma f}(x)$

$\gamma > 0$

$\iota_C(x)=\left\{\begin{aligned} & 0 &&\textrm{if $x \in C$}\\ &+\infty &&\textrm{otherwise}\end{aligned}\right.$ $\displaystyle P_C(x) = \operatorname*{argmin}_{y\in C}\, \|x-y\|$
$\displaystyle\sigma_C(x) = \sup_{y\in C}\, \langle x | y \rangle$ $x-\gamma P_C(x/\gamma)$
$d_C(x) = \|x-P_C(x)\|$ $\displaystyle\left\{\begin{aligned} &P_C(x) &&\textrm{if $d_C(x)\le \gamma$} \\[1em] &x+\gamma\dfrac{P_C(x)-x}{d_C(x)} &&\textrm{otherwise} \end{aligned}\right.$
$\dfrac{1}{2}d_C^2(x)$ $\dfrac{1}{1+\gamma}\Big(x+\gamma P_C(x)\Big)$
$\phi\big(d_C(x)\big)$

with $\phi\in\Gamma_0(\mathbb{R})$ even, and $\partial\phi(0)=\{0\}$

$\displaystyle\left\{\begin{aligned} &x &&\textrm{if $x\in C$} \\[1em] &x+\left(1-\dfrac{\operatorname{prox}_{\gamma\phi}\big(d_C(x)\big)}{d_C(x)}\right)\Big(P_C(x)-x\Big) &&\textrm{otherwise} \end{aligned}\right.$
$\iota_{\operatorname{lev}_\eta\varphi}(x)$

with $\operatorname{lev}_\eta \varphi = \{x\in\mathcal{H}\;|\;\varphi(x)\le\eta\}$ and $\varphi\in\Gamma_0(\mathcal{H})$

$\begin{cases} x &\textrm{if $\varphi(x) \leq \eta$}\\[1em] \operatorname{prox}_{\overline{\lambda}\, \varphi}(x) \scriptstyle\quad\textrm{with $\overline{\lambda} > 0$ such that $\varphi\Big( \operatorname{prox}_{\overline{\lambda} \varphi}(x) \Big)=\eta$} & \textrm{otherwise} \end{cases}$
$\iota_{\operatorname{epi} \varphi}(x,\zeta)$

with $\operatorname{epi} \varphi = \{ (x,\zeta) \in \mathcal{H}\times\mathbb{R} \;|\; \varphi(x) \le \zeta \}$ and $\varphi\in\Gamma_0(\mathcal{H})$

$\begin{cases} (x,\zeta) &\textrm{if $\varphi(x) \leq \zeta$}\\[1em] \big(p,\varphi(p)\big) \scriptstyle\quad\textrm{with $p = \operatorname{prox}_{\frac{1}{2}(\varphi-\zeta)^2}(x)$} & \textrm{otherwise} \end{cases}$

Projectors onto affine sets

$C$

$\mathcal{H}= \mathbb{R}^N$, $A\in\mathbb{R}^{K\times N}$, $b\in\operatorname{ran}(A)$

$P_C$

$x\in\mathbb{R}^{N}$, $u\in\mathbb{R}^{K}$

$\operatorname{ran}(A)=\{u\in\mathbb{R}^K \;|\; (\exists \, x \in \mathbb{R}^N)\; Ax=u\}$

with $\;\operatorname{rank}(A)=N$

$P_C(u) = A(A^\top A)^{−1}A^\top u$
$\operatorname{ker}(A) = \{x\in\mathbb{R}^N \;|\; Ax=0\}$

with $\;\operatorname{rank}(A)=K$

$P_C(x) = x - A^\top(A A^\top)^{−1}A x$
$\operatorname{aff}(A)=\{x\in\mathbb{R}^N \;|\; Ax=b\}$

with $\;\operatorname{rank}(A)=K$

$P_C(x) = x - A^\top(A A^\top)^{−1}(A x-b)$

Extensions

There exist several extensions of the previous definition.