Functions of a multivariate variable

Vector variable - Matrix variable - Perspective functions - Divergences

Vector variable

Description f(x)

(∀ x ∈ ℝN)

proxγf(x)

(∀ γ ∈ ℝ+)

Matlab Python Ref
Euclidean norm $\|x\|_2 = \displaystyle\sqrt{\sum_{n=1}^N x_n^2}$ $\left(1 - \dfrac{\gamma}{\max\big\{\|x\|_2,\gamma\big\}}\right)x$ [Function]
[Prox]
[Class] [Combettes et al., 2005]
Infinity norm $\|x\|_\infty = \displaystyle\max_{1\le n\le N} |x_n|$ $\Big(\operatorname{sign}(x_n)\min\{|x_n|,s\}\Big)_{1\le n\le N}$

where $s\in\mathbb{R}$ is such that $\displaystyle\sum_{n=1}^N \max\{0, |x_n| - s\} = \gamma$

[Function]
[Prox]
(coming soon)
Maximum $\displaystyle\max_{1\le n\le N} x_n$ $\Big(\min\{x_n,s\}\Big)_{1\le n\le N}$

where $s\in\mathbb{R}$ is such that $\displaystyle\sum_{n=1}^N \max\{0, x_n - s\} = \gamma$

[Function]
[Prox]
(coming soon)
Vapnik $\displaystyle\max\big\{\|x\|_2-\varepsilon\big\}$

(with $\varepsilon>0$)

$\left\{\begin{aligned} &x &&\textrm{if $\|x\|_2 - \varepsilon\le 0$}\\ &\frac{\varepsilon}{\|x\|_2}x &&\textrm{if $0<\|x\|_2-\varepsilon\le\gamma$}\\ &\Big(1-\frac{\gamma}{\|x\|_2}\Big) x &&\textrm{otherwise}\\ \end{aligned}\right.$ [Function]
[Prox]
(coming soon) [Combettes et al., 2011]

Matrix variable

Description f(X) = φ(s)

(∀ X = U Diag(s) V∈ ℝM × N)

proxγf(X)

(∀ γ ∈ ℝ+)

Matlab Python Ref
Permutation invariant $\varphi(s)$ $U\operatorname{Diag}\Big(\operatorname{prox}_{\gamma\varphi}(s)\Big)V^\top$ [Function]
[Prox]
(coming soon) [Lewis, 1996]
Nuclear norm $\displaystyle\|X\|_N = \|s\|_1$ $U\operatorname{Diag}\Big(\operatorname{prox}_{\gamma\|\cdot\|_1}(s)\Big)V^\top$ [Function]
[Prox]
(coming soon) [Lewis, 1996]
Frobenius norm $\displaystyle\|X\|_F = \|s\|_2$ $\operatorname{prox}_{\gamma\|\operatorname{Vec}(\cdot)\|_2}(X)$ [Function]
[Prox]
(coming soon) [Lewis, 1996]
Spectral norm $\displaystyle\|X\|_S = \|s\|_\infty$ $U\operatorname{Diag}\Big(\operatorname{prox}_{\gamma\|\cdot\|_\infty}(s)\Big)V^\top$ [Function]
[Prox]
(coming soon) [Lewis, 1996]

Perspective of convex functions

Description f(x,ξ)

(∀(x,ξ) ∈ ℝN×ℝ)

proxγf(x,ξ)

(∀ γ ∈ ℝ+)

Matlab Python Ref
Square $\begin{cases} \dfrac{\|x\|_2^2}{\xi} & \textrm{if $\xi > 0$}\\ 0 & \textrm{if $x = 0$ and $\xi=0$}\\ +\infty & \textrm{otherwise}.\end{cases}$ $\left\{\begin{aligned} &(0,0) &&\textrm{if $\|x\|_2^2\le -4\gamma\xi$}\\ &(0,\xi) &&\textrm{if $x=0$ and $\xi>0$}\\ &\Big(x-\dfrac{\gamma tx}{\|x\|_2}, \xi+\dfrac{\gamma t^2}{4}\Big) &&\textrm{otherwise} \end{aligned}\right.$

with $t\ge0$ such that

$\small \gamma t^3 + 4(\xi+2\gamma) t - 8\|x\|_2=0$
[Function]
[Prox]
(coming soon) [Combettes et al., 2017]
Squared root $\begin{cases} -\sqrt{\xi^2-\|x\|_2^2} & \textrm{if $\xi > 0$ and $\|x\|_2^2\le\xi$}\\ 0 & \textrm{if $x = 0$ and $\xi=0$}\\ +\infty & \textrm{otherwise}.\end{cases}$ $\left\{\begin{aligned} &\Big(x-\dfrac{\gamma tx}{\|x\|_2}, \xi+\gamma\sqrt{1+ t^2}\Big) &&\textrm{if $\xi+\sqrt{\gamma^2+\|x\|_2^2}>0$}\\ &(0,0) &&\textrm{otherwise} \end{aligned}\right.$

with $t\ge0$ such that

$\small 2\gamma t + \dfrac{\xi t}{\sqrt{1+t^2}} - \|x\|_2^2 = 0$

(assuming that $x/\|x\|_2=0$ if $x=0$)
[Function]
[Prox]
(coming soon) [Combettes et al., 2017]
Huber $\begin{cases} \rho|x|-\dfrac{\xi\rho^2}{2} & \textrm{if $\xi > 0$ and $|x|>\xi\rho$}\\ \dfrac{|x|^2}{2\xi} & \textrm{if $\xi > 0$ and $|x|\le\xi\rho$}\\ \rho|y| & \textrm{if $x = 0$}\\ +\infty & \textrm{if $x < 0$}\end{cases}$

(with $N=1$ and $\rho>0$)

$\left\{\begin{aligned} &(0,0) &&\textrm{if $2\gamma\xi+|x|^2\le0$ and $|y|\le\gamma\rho$}\\ &\Big(x-\gamma\rho\operatorname{sign}(x),0\Big) &&\textrm{if $\xi\le -\gamma\rho^2/2$ and $|x|>\gamma\rho$}\\ &\Big(x-\gamma\rho\operatorname{sign}(x),\xi+\gamma\rho^2/2\Big) &&\textrm{if $\xi>-\gamma\rho^2/2$ and $|x|>\rho\xi+\gamma\rho(1+\rho^2/2)$}\\ &\operatorname{prox}_{\gamma|\cdot|^2/(\cdot)}(x,\xi) &&\textrm{if $\xi>-\gamma\rho^2/2$ and $|x|\le\rho\xi+\gamma\rho(1+\rho^2/2)$} \end{aligned}\right.$ [Function]
[Prox]
(coming soon) [Combettes et al., 2017]
Vapnik $\begin{cases} \displaystyle\inf_{y\in\mathbb{R}} \; |y| + \iota_{[-\varepsilon\xi,\varepsilon\xi]}(x-y) & \textrm{if $\xi \ge 0$}\\ +\infty & \textrm{if $\xi < 0$}\end{cases}$

(with $N=1$ and $\rho>0$)

$\left\{\begin{aligned} &(0,0) &&\textrm{if $\xi+\varepsilon|x|\le0$ and $|x|\le\gamma$}\\ &\Big(x-\gamma\operatorname{sign}(x),0\Big) &&\textrm{if $\xi\le-\gamma\varepsilon$ and $|x|>\gamma$}\\ &\Big(x-\gamma\operatorname{sign}(x),\xi+\gamma\varepsilon\Big) &&\textrm{if $\xi>-\gamma\varepsilon$ and $|x|>\varepsilon\xi+\gamma(1+\varepsilon^2)$}\\ &\Big(\varepsilon(\xi+\varepsilon|x|)\operatorname{sign}(x)/(1+\varepsilon^2),(\xi+\varepsilon|x|)/(1+\varepsilon^2)\Big) &&\textrm{if $|x|>-\xi/\varepsilon$ and $\varepsilon\xi\le|x|\le\varepsilon\xi+\gamma(1+\varepsilon^2)$}\\ &(y,\xi) &&\textrm{if $\xi\ge0$ and $|x|\le\varepsilon\xi$} \end{aligned}\right.$ [Function]
[Prox]
(coming soon) [Combettes et al., 2017]

φ-divergences

Description f(x,y)

(∀(x,y) ∈ ℝ2)

proxγf(x,y)

(∀ γ ∈ ℝ+)

Matlab Python Ref
Absolute
difference
$\left\{\begin{aligned} &|x-y| && \mbox{if $x\ge0$ and $y\ge0$}\\ &+\infty && \mbox{otherwise}\end{aligned}\right.$ $\small\left\{\begin{aligned} &\frac12\big(x+y+p,x+y-p\big) && \mbox{if $|p| < x+y$}\\ &(x-\gamma,0) && \mbox{if $x > \gamma$ and $y \le -\gamma$}\\ &(0,y-\gamma) && \mbox{if $y > \gamma$ and $x \le -\gamma$}\\ &(0,0) && \mbox{otherwise} \end{aligned}\right.$

where

$\small p=\operatorname{sign}(x-y)\max\big\{|x-y|-2\gamma,0\big\}$
[Function]
[Prox]
(coming soon) [El Gheche et al., 2018]
Hellinger $\left\{\begin{aligned}&(\sqrt{x}-\sqrt{y})^2 && \mbox{if $x\ge0$ and $y\ge0$}\\ &+\infty && \mbox{otherwise.}\end{aligned}\right.$ $\small\left\{\begin{aligned} &\Big(x + \gamma (p-1),y+\gamma \big(p^{-1}-1\big)\Big) &&\mbox{if $x \ge \gamma$ or $\left(1-\dfrac{x}{\gamma}\right) \left(1-\dfrac{y}{\gamma}\right) < 1$}\\[1em] &(0,0) && \mbox{otherwise} \end{aligned}\right.$

where

$\small\; p>\max\left\{1-\dfrac{x}{\gamma},0\right\}\;$

is such that

$\small p^{4}+ \left(\dfrac{x}{\gamma}-1\right)p^3 + \left(1-\dfrac{y}{\gamma}\right)p-1= 0$
[Function]
[Prox]
(coming soon) [El Gheche et al., 2018]
Chi-square $ \left\{\begin{aligned} &\dfrac{(x-y)^2}{y} &&\textrm{if $x \ge 0$ and $y>0$}\\ &0 &&\textrm{if $x = y = 0$}\\ &+\infty &&\textrm{otherwise}\end{aligned}\right.$ $\small \left\{\begin{aligned} &\Big(x + 2 \gamma(1-p),y+\gamma (p^2-1)\Big) &&\mbox{if $x > -2\gamma$ and $y > - \left(x+\frac{1}{4\gamma}x^2\right)$}\\[1em] &\big(0,\max\{y-\gamma,0\}\big) && \mbox{otherwise} \end{aligned}\right.$

where

$\small\; p \in \left]0,1+\dfrac{x}{2\gamma}\right[ \;$

is such that

$\small p^3+\left(1+\dfrac{y}{\gamma}\right)p - \dfrac{x}{\gamma} -2 = 0$
[Function]
[Prox]
(coming soon) [El Gheche et al., 2018]
Kullback-Leibler $ \left\{\begin{aligned} &x \log\Big(\dfrac{x}{y}\Big) && \mbox{if $x>0$ and $y>0$}\\ &0 &&\mbox{if $x=0$ and $y \ge 0$}\\ &+\infty && \mbox{otherwise}\end{aligned}\right.$ $\small \left\{\begin{aligned} &\Big(x + \gamma \log(p) -\gamma,y+\gamma p^{-1}\Big) && \mbox{if $\exp\left(\dfrac{x}{\gamma}-1\right) > -\dfrac{y}{\gamma}$}\\[1em] &(0,0) && \mbox{otherwise} \end{aligned}\right.$

where

$\small\; p>\exp\left(-\dfrac{x}{\gamma}-1\right) \;$

is such that

$\small\;p \log(p) + \left(\dfrac{x}{\gamma}-1\right)p - p^{-1} - \dfrac{y}{\gamma} = 0$
[Function]
[Prox]
(coming soon) [El Gheche et al., 2018]
Jeffrey $\small \left\{\begin{aligned}&(x-y) \Big(\log(x)-\log(y)\Big) && \mbox{if $x>0$ and $y>0$}\\ &0 && \mbox{if $x=y=0$}\\ &+\infty && \mbox{otherwise.}\end{aligned}\right.$ $\small \begin{cases} \Big(x + \gamma \big(\log(p) + p-1),y-\gamma \big(\log(p) -p^{-1}+1)\Big) &\mbox{if $W(e^{1-\gamma^{-1}x})W(e^{1 - \gamma^{-1}y}) < 1$}\\[1em] (0,0) & \mbox{otherwise} \end{cases}$

where

$\small\; p\in\left[W(e^{1-\gamma^{-1}x}),\Big(W(e^{1 - \gamma^{-1}y})\Big)^{-1}\right] \;$

is such that

$\small (p+1) \log(p) - p^{-1} + p^2 + \Big(\dfrac{x}{\gamma}- 1\Big) p + 1 - \dfrac{y}{\gamma} = 0$
[Function]
[Prox]
(coming soon) [El Gheche et al., 2018]
Rényi $ \left\{\begin{aligned} &\dfrac{x^\alpha}{y^{\alpha-1}} &&\textrm{if $x \ge 0$ and $y>0$}\\ &0 &&\textrm{if $x = y = 0$}\\ &+\infty &&\textrm{otherwise}\end{aligned}\right.$ $\small \left\{\begin{aligned} &\left(x - \frac{\gamma \alpha}{ p^{\alpha-1}},y+ \frac{\gamma (\alpha-1)}{p^{\alpha}}\right) &&\mbox{if $x>0$ and $\dfrac{\gamma^{\frac{1}{\alpha-1}} \, y}{1-\alpha} < \left(\dfrac{x}{\alpha}\right)^{\frac{\alpha}{\alpha-1}}$ }\\[1em] &\big(0,\max\{y,0\}\big) && \mbox{otherwise} \end{aligned}\right.$

where

$\small\; p > \Big(\dfrac{\alpha \gamma}{x}\Big)^{\frac{1}{\alpha-1}} \;$

is such that

$\small\dfrac{x}{\gamma}\;p^{\alpha+1} - \dfrac{y}{\gamma}\,p^{\alpha} - \alpha p^{2} + 1-\alpha = 0$
[Function]
[Prox]
(coming soon) [El Gheche et al., 2018]
$I_\alpha$ $ \left\{\begin{aligned} &-\sqrt[\alpha]{x \, y^{\alpha-1}} &&\textrm{if $x \ge 0$ and $y\ge0$}\\ &+\infty &&\textrm{otherwise}\end{aligned}\right.$ $\small \left\{\begin{aligned} &\left(x +\frac{\gamma}{\alpha}\big(p^{\alpha-1}-1\big),y + \frac{\gamma(\alpha-1)}{\alpha} \big(p^{-1}-1\big)\right) &&\mbox{if $\alpha x \ge \gamma\;$ or $\;1-\frac{\alpha y}{\gamma(\alpha - 1)}<\left(\frac{\gamma}{\gamma-\alpha x}\right)^{\frac{1}{\alpha-1}}$}\\[1em] &(0,0) && \mbox{otherwise} \end{aligned}\right.$

where

$\small\; p > \left(\max\Big\{1- \dfrac{\alpha x}{\gamma},0\Big\}\right)^{\frac{1}{\alpha-1}}\;$

is such that

$\small p^{2\alpha} + \left(\dfrac{\alpha x}{\gamma}-1\right) p^{\alpha+1} + \left(\alpha-1-\dfrac{\alpha y}{\gamma}\right) p -\alpha+1=0$
[Function]
[Prox]
(coming soon) [El Gheche et al., 2018]