Definition - Properties - Special functions - Affine sets - Extensions
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.
$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)$ |
$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}$ |
$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)$ |