Indicator functions

Polyhedra - Lower-level sets - Epigraphs

Python users do NOT need to download the files, they can directly use our Python library proxop . To install proxop containing the proximity of all functions in this repository, you can run the following command in the Python terminal:

pip install proxop

The name of a class in the library is the same as the one indicated in the column 'Python' of this following table. For example, to compute the projection onto the constrained box $[\eta_1=-2, \eta_2=2]^N$:

from proxop import BoxConstraint
import numpy as np

x = np.array([-5, 1, 10., 0, 3])
BoxConstraint(-2., 2.).prox(x)
# result: array([-2.,  1.,  2.,  0.,  2.])

For the majority of the functions $f$ in the library, one can compute the proximity operator of their scaled version $\gamma f$ (with $\gamma > 0$) by simply using the parameter 'gamma' in the method prox.(default value: gamma=1).

Example: Compute the proximity operator of the scaled version of the absolute value function:

from proxop import AbsValue

x = np.array([ -3., 1., 6.])

AbsValue().prox(x, gamma=2)
#result: array([-1.,  0.,  4.])

Polyhedra

Name C ⊂ ℝN

(∀ x ∈ ℝN)

PC(x) Matlab Python Ref
Box $x \in [\eta_1, \eta_2]^N$

(with $\eta_1<\eta_2$)

$\Big[\max\big\{\eta_1,\min\{x_n,\eta_2\}\big\}\Big]_{1\le n\le N}$ [Function]
[Prox]
[BoxConstraint]
Hyperplane $u^\top x = \eta$

(with $(u,\eta)\in\mathbb{R}^N\times \mathbb{R}$)

$x+\dfrac{\eta - u^\top x }{\|u\|_2^2}u$ [Function]
[Prox]
[Hyperplane]
Hyperslab $\eta_1 \le u^\top x \le \eta_2$

(with $\eta_1<\eta_2$)

$\left\{ \begin{aligned} &x+\dfrac{\eta_1- u^\top x }{\|u\|_2^2}u &&\quad \textrm{if $u^\top x<\eta_1$}\\[1em] &x+\dfrac{\eta_2-u^\top x}{\|u\|_2^2}u &&\quad \textrm{if $u^\top x > \eta_2$}\\[1em] &x &&\quad \textrm{otherwise}\\ \end{aligned}\right.$ [Function]
[Prox]
[Hyperslab]
Simplex $\begin{cases}x\in[0,+\infty[^N \\{\rm 1}^\top x = \eta\end{cases}$

(with $(1,\eta)\in\mathbb{R}^N\times \mathbb{R}$)

$\big[\max\{0,x_n-\lambda\}\big]_{1\le n\le N}$

with $\lambda\in\mathbb{R}$ such that $\displaystyle \sum_{n=1}^N \max\{0,x_n-\lambda\} = \eta$

[Function]
[Prox]
[Mex-file]
[Simplex] [Michelot, 1986]
[Condat, 2016]
Extended simplex $\begin{cases}x\in[0,+\infty[^N \\{\rm 1}^\top x \leq \eta\end{cases}$

(with $(1,\eta)\in\mathbb{R}^N\times \mathbb{R}$)

$\begin{cases} \mathrm{max}(x,0) & \mathrm{if} \quad {\rm 1}^\top (\mathrm{max}(x,0)) \leq \eta \\ \mathrm{P}_{\{x | x \geq 0 \; \mathrm{and}\; {\rm 1}^\top x = \eta\}}(x) & \mathrm{otherwise} \end{cases}$ [Function]
[Prox]
[ExtendedSimplex] [Michelot, 1986]
[Condat, 2016]
Monotone cone $x_1 \le x_2 \le\dots\le x_N$ $\displaystyle\left[\max_{1\le j\le n}\;\min_{n\le k\le N}\;\frac{1}{k-j+1}\sum_{\ell=j}^k x_\ell\right]_{1\le n\le N}$ [Function 1, Function 2]
[Prox 1, Prox 2]
[MonotoneCone] [Ayer et al., 1955]

Lower-level sets

Name C ⊂ ℝN

(∀ x ∈ ℝN)

PC(x) Matlab Python Ref
$\ell_1$-ball $\|x\|_1 \le \eta$

(with $\eta\ge0$)

$x - \operatorname{prox}_{\eta\|\cdot\|_\infty}(x)$ [Function]
[Prox]
[L1Ball] [van den Berg et al., 2008]
$\ell_2$-ball $\|x\|_2 \le \eta$

(with $\eta\ge0$)

$x - \operatorname{prox}_{\eta\|\cdot\|_2}(x)$ [Function]
[Prox]
[L2Ball] [Combettes et al., 2005]
Positive $\ell_2$-ball $\|x\|_2 \le \eta$ and $x \geq 0$

(with $\eta\ge0$)

$ \begin{cases} \mathrm{max}(x,0) & \text{if } \| \mathrm{max}(x,0)\|_2 \leq \eta\\ \frac{\eta}{ \| \mathrm{max}(x,0)\|_2} \mathrm{max}(x,0) & \text{otherwise} \end{cases} $ [Function]
[Prox]
[PositiveL2Ball] [Combettes, 2018]
$\ell_\infty$-ball $\|x\|_\infty \le \eta$

(with $\eta\ge0$)

$P_{[-\eta,\eta]^N}(x) = \Big[\operatorname{sign}(x_n)\min\{|x_n|,\eta\}\Big]_{1\le n\le N}$ [Function]
[Prox]
[ LinfBall]
$\ell_{1,2}$-ball $\displaystyle\sum_{b=1}^B \|x^{(b)}\|_{2} \le \eta$

(with $x = \big[{x^{(1)}}^\top\,\dots\,{x^{(B)}}^\top\big]^\top$ and $\eta\ge0$)

$\left[p^{(b)}\right]_{1\le b\le B}$

with

$p^{(b)} =\begin{cases}0 &\textrm{if $\|x^{(b)}\|_2=0$}\\[1em] x^{(b)}\dfrac{\beta_b}{\|x^{(b)}\|_2} &\textrm{otherwise}\end{cases}$

and

$(\beta_1,\dots,\beta_B) = P_{\{\|\cdot\|_1\le\eta\}}\Big(\|x^{(1)}\|_2,\dots,\|x^{(B)}\|_2\Big)$
[Function]
[Prox]
[ L1_2Ball] [van den Berg et al., 2008]
Logarithm $\displaystyle \sum_{n=1}^N -\log x_n \le \eta$

(with $\eta\in\mathbb{R}$)

$\begin{cases} x &\textrm{if $\;\displaystyle\sum_{n=1}^N -\log x_n \leq \eta$}\\[1em] \left(\dfrac{x_n + \sqrt{x_n^2 + 4\overline{\lambda}}}{2}\right)_{1\le n\le N} & \textrm{otherwise} \end{cases}$

with $\overline{\lambda} > 0$ such that

$\displaystyle\sum_{n=1}^N -\log \left(\dfrac{x_n + \sqrt{x_n^2 + 4\overline{\lambda}}}{2}\right) =\eta$
[Function]
[Prox]
[LogProjection] [Carlavan et al., 2011]

Epigraphs

Name φ(y) Pepiφ(y,ζ) Matlab Python Ref
Support function $\sigma_{\left[a,b\right]}(y)$

(with $y\in\mathbb{R}$ and $a< b$)

$\left\{\begin{aligned} &(y,\zeta) &&\textrm{if $\;a y \le \zeta\;$ and $\;b y \le \zeta$}\\[0.5em] &\big(1,b\big)\frac{y+b\zeta}{1+b^2} &&\textrm{if $\;b y > \zeta\;$ and $\;-\frac{y}{b} \le \zeta$}\\[0.5em] &\big(1,a\big)\frac{y+a\zeta}{1+a^2} &&\textrm{if $\;a y > \zeta\;$ and $\;-\frac{y}{a} \le \zeta$}\\[0.5em] &(0,0) && \textrm{otherwise}\end{aligned}\right.$ [Function]
[Prox]
[ EpiSupport ]
Absolute value $\tau |y|$

(with $y\in\mathbb{R}$ and $\tau > 0$)

$\left\{\begin{aligned} &(y,\zeta) &&\textrm{if $\tau |y| \le \zeta$}\\[0.5em] &\Big(\operatorname{sign}(y),\tau\Big)\frac{\max\{0,|y|+\tau\zeta\}}{1+\tau^2} &&\textrm{otherwise} \end{aligned}\right.$ [Function]
[Prox]
[ EpiAbsValue] [Chierchia et al., 2015]
Power $\tau |y|^q$

(with $y\in\mathbb{R}$ and $\tau > 0$)

$\left\{\begin{aligned} &(y,\zeta) &&\textrm{if $\tau |y|^q \le \zeta$}\\[0.5em] &\Big(\operatorname{sign}(y)p,\tau |p|^q\Big) &&\textrm{otherwise} \end{aligned}\right.$

with $\small p\ge\sqrt[q]{\frac{\max\{\zeta,0\}}{\tau}}$ such that

$\small q\tau^2 p^{2q-1} - q\tau\zeta p^{q-1} + p - |y| = 0$
[Function]
[Prox]
[ EpiPower ] [Chierchia et al., 2015]
Hinge loss $\tau \max\{y, 0\}$

(with $y\in\mathbb{R}$ and $\tau > 0$)

$\left\{\begin{aligned} &(y,\zeta) &&\textrm{if $\;\tau\max\{y,0\}\le\zeta$}\\[0.5em] &(y,0) && \textrm{if $\;\tau\max\{y,0\}>\zeta\;$ and $\;y\le0$}\\[0.5em] &\big(1,\tau\big)\frac{\max\{0,y+\tau\zeta\}}{1+\tau^2} &&\textrm{otherwise}\\ \end{aligned}\right.$ [Function]
[Prox]
[ EpiHingeLoss]
Squared hinge loss $\tau\left(\max\{y,0\}\right)^2$

(with $y\in\mathbb{R}$ and $\tau > 0$)

$\left\{\begin{aligned} &(y,\zeta) &&\textrm{if $\;\tau \left(\max\{y,0\}\right)^2 \le \zeta$}\\[0.5em] &(y,0) &&\textrm{if $\;\tau \left(\max\{y,0\}\right)^2 > \zeta\;$ and $\;y\le0$}\\[0.5em] &P_{\{\operatorname{epi}\tau|\cdot|^2\}}(y,\zeta) &&\textrm{otherwise} \end{aligned}\right.$ [Function]
[Prox]
[ EpiSquaredHingeLoss]
Logarithm $\begin{cases}-\tau\log(y) &\textrm{if $y>0$}\\+\infty&\textrm{otherwise}\end{cases}$

(with $y\in\mathbb{R}$ and $\tau > 0$)

$\left( \dfrac{y + \sqrt{y^2 + 4\tau\lambda}}{2}, \zeta+\lambda \right)$

with $\small \lambda\ge0$ such that

$-\tau\log\left(\frac{y + \sqrt{y^2 + 4\tau\lambda}}{2}\right) - \zeta-\lambda = 0$
[Function]
[Prox]
[EpiLog ] [Wang et al., 2016]
Exponential $\tau\exp(y)$

(with $y\in\mathbb{R}$ and $\tau > 0$)

$\left\{\begin{aligned} &(y,\zeta) && \textrm{if $\tau\exp(y)\le\zeta$}\\[0.5em] &\big( \log(p/\tau), p \big) && \textrm{otherwise} \end{aligned}\right.$

with $\small p>\max\{0,\zeta\}$ such that

$p^2-\zeta p + \log(p) - y = 0$
[Function]
[Prox]
[EpiExp ] [El Gheche et al., 2016]
Distance function $\tau d^{q}_C(y)$

(with $y\in\mathbb{R}^N$, $\tau > 0$, $q\ge1$, $C\subset\mathbb{R}^N$)

$\left\{\begin{aligned} &(y,\zeta) &&\quad \textrm{if $\;\tau d^q_C(y) \le \zeta$}\\[0.5em] &(y,0) &&\quad \textrm{if $\;d_C(y) = 0\;$ and $\;\zeta<0$}\\[0.5em] &\Big(p,\tau d^q_C(p)\Big) &&\quad\textrm{otherwise} \end{aligned}\right.$

where $\small p=P_C(y) + \dfrac{t}{d_C(y)} \Big(y-P_C(y)\Big)$ and

if $q=1$, then $t = \dfrac{\max\{0,d_C(y)+\tau\zeta\}}{1+\tau^2}$

if $q>1$, then $t\ge\sqrt[q]{\frac{\max\{\zeta,0\}}{\tau}}$ is such that: $q\tau^2 t^{2q-1} - q\tau\zeta t^{q-1} + t - d_C(y) = 0$

[Function]
[Prox]
[ EpiDistance] [Chierchia et al., 2015]
Euclidean norm $\tau\|y\|_2$

(with $y\in\mathbb{R}^N$ and $\tau > 0$)

$\left\{\begin{aligned} &(y,\zeta) &&\quad \textrm{if $\;\tau \|y\|_2 \le \zeta$}\\[0.5em] &(0,0) &&\quad \textrm{if $\;y=0\;$ and $\;\zeta<0$}\\[0.5em] &\Big(y,\tau \|y\|_2\Big)\dfrac{\max\{0,\|y\|_2+\tau\zeta\}}{(1+\tau^2)\|y\|_2} &&\quad\textrm{otherwise} \end{aligned}\right.$ [Function]
[Prox]
[ EpiL2Norm]
Infinity norm $\tau\|y\|_\infty$

(with $y\in\mathbb{R}^N$ and $\tau > 0$)

$\Big[\operatorname{sign}(y_n)\min\big\{|y_n|,\max\{\theta/\tau,0\}\big\}\Big]_{1\le n\le N}$

where

$(\nu_n)_{1\le n\le N}$ are the values $(\tau \, |y_n|)_{1\le n\le N}$ sorted in ascending order

$\theta = \dfrac{1}{\tau^2+N-\overline{n}+1}\left(\tau^2\zeta+\displaystyle\sum_{n=\overline{n}}^N \nu_n\right)$

$\overline{n}\in\{1,\dots,M+1\}$ is such that $\nu_{\overline{n}-1} < \theta \le \nu_{\overline{n}}$

[Function]
[Prox]
[EpiLinfNorm ] [Chierchia et al., 2015]
Max function $\displaystyle\tau\max_{1\le n\le N}\, y_n$

(with $y\in\mathbb{R}^N$ and $\tau > 0$)

$\Big[\min\{y_n,\theta/\tau\}\Big]_{1\le n\le N}$

where

$(\nu_n)_{1\le n\le N}$ are the values $(\tau \, y_n)_{1\le n\le N}$ sorted in ascending order

$\theta = \dfrac{1}{\tau^2+N-\overline{n}+1}\left(\tau^2\zeta+\displaystyle\sum_{n=\overline{n}}^N \nu_n\right)$

$\overline{n}\in\{1,\dots,M+1\}$ is such that $\nu_{\overline{n}-1} < \theta \le \nu_{\overline{n}}$

[Function]
[Prox]
[ EpiMax] [Chierchia et al., 2015]