Nonconvex functions

Scalar variable - Vector variable - Complex variable

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' of 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.])

Scalar variable

Description f(x)

(∀ x ∈ ℝ)

proxγf(x)

(∀ γ ∈ ℝ+)

Matlab Python Ref
$\ell_0$-norm $|x|^0 =\left\{\begin{aligned} &0 &&\textrm{if $x=0$}\\ &1 &&\textrm{otherwise}\end{aligned}\right.$ $\operatorname{hard}_{\sqrt{2\gamma}}(x) = \left\{\begin{aligned} &0 &&\quad \textrm{if $\;x^2 < 2\gamma$}\\ &\{x,0\} &&\quad \textrm{if $\;x^2 = 2\gamma$}\\ &x &&\quad \textrm{otherwise} \end{aligned}\right.$ [Function]
[Prox]
[L0Norm] [Combettes et al., 1990][Blumensath et al., 2009]
Truncated $\min\{x^2,\omega\}$ $\left\{\begin{aligned} &\frac{x}{1+2\gamma} &&\quad \textrm{if $x^2 < \omega(1+2\gamma)$}\\[0.5em] &\left\{x,\frac{x}{1+2\gamma}\right\} &&\quad \textrm{if $x^2 = \omega(1+2\gamma)$}\\[0.5em] &x &&\quad \textrm{otherwise} \end{aligned}\right.$ [Function]
[Prox]
[Truncated] [Strekalovskiy et al., 2014]
Log-sum $\log(\delta+|x|)$

(with $\delta>0$)

$\left\{\begin{aligned} &0 &&\quad \textrm{if $|x| < \sqrt{4\gamma} - \delta$}\\ &\left\{0,\operatorname{sign}(x)\dfrac{|x| - \delta + \sqrt{(|x|+\delta)^2 - 4\gamma}}{2}\right\} &&\quad \textrm{if $|x| = \sqrt{4\gamma} - \delta$}\\ &\operatorname{sign}(x)\dfrac{|x| - \delta + \sqrt{(|x|+\delta)^2 - 4\gamma}}{2} &&\quad \textrm{otherwise} \end{aligned}\right.$ [Function]
[Prox]
[LogSum]
Cauchy $\log(\delta+x^2)$

(with $\delta>0$)

$\displaystyle\operatorname*{Argmin}_{p\in \mathbb{R} \;\textrm{s.t.}\; \psi(p)=0}\quad \frac{1}{2\gamma} (x-p)^2 + f(p)$

with

$\psi(p)= p^3 -x p^2 + (\delta + 2\gamma) p -x\delta$
[Function]
[Prox]
[Cauchy]
Root $|x|^{q}$

(with $0< q< 1$)

$\left\{\begin{aligned} &0 &&\textrm{if $\gamma |x|^{q-2} > \dfrac{1}{2-q}\left(2\dfrac{1-q}{2-q}\right)^{1-q}$}\\ &tx &&\textrm{otherwise} \end{aligned}\right.$

with $\scriptsize t>0$ such that

$\gamma |x|^{q-2} \, q \, t^{q-1} + t-1 = 0$
[Function]
[Prox]
[Root] [Bredies et al., 2008]
Burg + log-sum $\left\{\begin{aligned} &-\log(x) + \omega \log(\delta+x) &&\textrm{if $x>0$}\\ &+\infty &&\textrm{otherwise}\end{aligned}\right.$

(with $\omega>0$ and $\delta>0$)

$\displaystyle\operatorname*{Argmin}_{p\in ]0,+\infty[ \;\textrm{s.t.}\; \psi(p)=0}\quad \frac{1}{2\gamma} (x-p)^2 + f(p)$

with

$\psi(p)=p^3 + (\delta-x)p^2 + (\omega\gamma-\delta x-\gamma) p -\delta\gamma$
[Function]
[Prox]
[BurgLogSum] [Cherni et al., 2016]
Burg + Cauchy $\left\{\begin{aligned} &-\log(x) + \omega \log(\delta+x^2) &&\textrm{if $x>0$}\\ &+\infty &&\textrm{otherwise}\end{aligned}\right.$

(with $\omega>0$ and $\delta>0$)

$\displaystyle\operatorname*{Argmin}_{p\in ]0,+\infty[ \;\textrm{s.t.}\; \psi(p)=0}\quad \frac{1}{2\gamma} (x-p)^2 + f(p)$

with

$\psi(p)=p^4 - xp^3 + (\delta + 2\gamma\omega - \gamma)p^2 - \delta xp - \delta\gamma$
[Function]
[Prox]
[BurgCauchy] [Cherni et al., 2016]
Entropy + $\ell_0$ $\left\{\begin{aligned} &x\log(x)+\omega &&\textrm{if $x>0$}\\ &0 &&\textrm{if $x=0$}\\ &+\infty &&\textrm{otherwise}\end{aligned}\right.$

(with $\omega>0$)

$\left\{\begin{aligned} &0 &&\quad \textrm{if $p^2+ 2\gamma p < 2\omega\gamma$}\\[0.5em] &\{p,0\} &&\quad \textrm{if $p^2+ 2\gamma p = 2\omega\gamma$}\\[0.5em] &p \scriptstyle\quad\textrm{with $\; p=\gamma \,W\left(\frac{1}{\gamma}\exp\Big(\frac{x}{\gamma}-1\Big)\right)$} &&\quad \textrm{otherwise} \end{aligned}\right.$ [Function]
[Prox]
[EntropyL0] [Cherni et al., 2016]
Entropy + log-sum $\left\{\begin{aligned} &x\log(x) + \omega \log(\delta+x) &&\textrm{if $x>0$}\\ &\omega \log(\delta) &&\textrm{if $x=0$}\\ &+\infty &&\textrm{otherwise}\end{aligned}\right.$

(with $\omega>0$ and $\delta>0$)

$\displaystyle\operatorname*{Argmin}_{p\in ]0,+\infty[ \;\textrm{s.t.}\; \psi(p)=0}\quad \frac{1}{2\gamma} (x-p)^2 + f(p)$

with

$\psi(p)= p^2 + (\delta-x+\gamma)p + \gamma(\delta + p)\log(p)+\delta(\gamma-x) +\omega\gamma$
[Function]
[Prox]
[EntropyLogSum] [Cherni et al., 2016]
Entropy + Cauchy $\left\{\begin{aligned} &x\log(x) + \omega \log(\delta+x^2) &&\textrm{if $x>0$}\\ &\omega \log(\delta) &&\textrm{if $x=0$}\\ &+\infty &&\textrm{otherwise}\end{aligned}\right.$

(with $\omega>0$ and $\delta>0$)

$\displaystyle\operatorname*{Argmin}_{p\in ]0,+\infty[ \;\textrm{s.t.}\; \psi(p)=0}\quad \frac{1}{2\gamma} (x-p)^2 + f(p)$

with

$\psi(p)=p^3 + (\gamma-x)p^2 + (\delta + 2\gamma\omega)p + \gamma(\delta+p^2)\log(p) + \delta(\gamma-x)$
[Function]
[Prox]
[EntropyCauchy] [Cherni et al., 2016]
Capped $\ell_1$ $\mathrm{min}\{\theta |x|,1\}$

(with $\theta>0$)

$ \left\lbrace \begin{array}{ll} x 1_{\{|x| > \sqrt{2\gamma}\}} + \{0,x\} 1_{\{|x| = \sqrt{2\gamma}\}} & \text{ if } \gamma \theta^2 \geqslant 2 \\ \mathrm{sign}(x) (|x| - \gamma \theta)1_{\{ \gamma \theta < |x| < \frac{1}{\theta} + \frac{\gamma \theta}{2}\}} + x 1_{\{|x| \geq \frac{1}{\theta} + \frac{\gamma \theta}{2}\}} & \text{ if } \gamma \theta^2 < 2 \end{array} \right.$ [Function]
[Prox]
[CapL1] [Zhang, 2009]
SCAD $ \left\lbrace \begin{array}{ll} \lambda |x| & \text{ if } |x| \leqslant \lambda \\ - \frac{\lambda^2 - 2 a \lambda |x| + x^2}{2(a-1)} & \text{ if } \lambda < |x| \leq a \lambda \\ \frac{(a+1)\lambda^2}{2} & \text{ if } |x| > a \lambda \end{array} \right.$

(with $a >2$, $\lambda >0$)

$\bullet$ if $a > 1+ \gamma$:

$\left\lbrace \begin{array}{ll} \mathrm{sign}(x) \mathrm{max}(|x|-\lambda \gamma,0) & \text{ if } |x| \leqslant (1+\gamma)\lambda \\ \frac{(a-1)x - \mathrm{sign}(x) a \lambda \gamma}{a-1-\gamma}& \text{ if } (1+\gamma)\lambda < |x| \leqslant a \lambda \\ x & \text{ if } |x| > a \lambda \end{array}\right.$

$\bullet$ if $a \leqslant 1+ \gamma$:

$\left\lbrace \begin{array}{ll} \mathrm{sign}(x) \mathrm{max}(|x|-\lambda \gamma,0) & \text{ if } |x| \leqslant 0.5(a+1+\gamma)\lambda \\ x & \text{ if } |x| > 0.5(a+1+\gamma)\lambda \end{array}\right. $
[Function]
[Prox]
[SCAD] [Fan et al, 2001]
MCP $\left\lbrace \begin{array}{ll} \lambda |x| - \frac{x^2}{2 \beta} & \text{ if } |x| \leqslant \beta \lambda \\ \frac{\beta \lambda^2}{2} & \text{ if } |x| > \beta \lambda \end{array}\right. $

(with $\beta >0$, $\lambda>0$)

$\left\lbrace \begin{array}{ll} x 1_{\{|x| > \sqrt{\gamma \beta} \lambda\}} + \{0,x\} 1_{\{|x| = \sqrt{\gamma \beta} \lambda\}} & \text{ if } \beta \leqslant \gamma \\ \mathrm{sign}(x) \mathrm{min} \{ \frac{\beta \mathrm{max} \{|x| - \lambda \gamma,0\}}{\beta - \gamma} , |x| \}& \text{ if } \beta > \gamma \end{array}\right. $ [Function]
[Prox]
[MCP] [Zhang, 2010]
CEL0 $ \lambda - \frac{a^2}{2} \left(|x| - \frac{\sqrt{2\lambda}}{a} \right)^2 1_{\{|x| \leqslant \frac{\sqrt{2\lambda}}{a}\}} $

(with $\lambda >0$ and $a>0$)

$\left\lbrace \begin{array}{ll} \mathrm{sign}(x) \min \left\lbrace |x|, \frac{\max\{|x| - \sqrt{2\lambda}\gamma a,0\}}{1-a^2 \gamma} \right\rbrace & \text{ if } a^2 \gamma < 1 \\ x 1_{\{|x| > \sqrt{2\gamma \lambda}\}} + \{0,x\} 1_{\{|x| = \sqrt{2\gamma \lambda}\}} & \text{ if } a^2 \gamma \geqslant 1 \end{array}\right.$ [Function]
[Prox]
[CEL0] [Soubies et al, 2015]

Vector variable

Name f(x)

(∀ x ∈ ℝN)

proxγf(x)

(∀ γ ∈ ℝ+)

Matlab Python Ref
$\ell_{0,2}$-norm $\|x\|_2^0 =\left\{\begin{aligned} &0 &&\textrm{if $\|x\|_2=0$}\\ &1 &&\textrm{otherwise}\end{aligned}\right.$ $\left\{\begin{aligned} &0 &&\quad \textrm{if $\;\|x\|_2^2 < 2\gamma$}\\ &\{x,0\} &&\quad \textrm{if $\;\|x\|_2^2 = 2\gamma$}\\ &x &&\quad \textrm{otherwise} \end{aligned}\right.$ [Function]
[Prox]
[L0L2Norm] [Xu et al., 2011]
Truncated norm $\min\{\|x\|_2^2,\omega\}$

(with $\omega>0$)

$\left\{\begin{aligned} &\frac{x}{1+2\gamma} &&\quad \textrm{if $\|x\|_2^2 < \omega(1+2\gamma)$}\\[0.5em] &\left\{x,\frac{x}{1+2\gamma}\right\} &&\quad \textrm{if $\|x\|_2^2 = \omega(1+2\gamma)$}\\[0.5em] &x &&\quad \textrm{otherwise} \end{aligned}\right.$ [Function]
[Prox]
[TruncatedNorm] [Strekalovskiy et al., 2014]

Complex variable

Name f(x,d)

(∀ (x,d) ∈ ℂ2)

proxγf(x)

(∀ γ ∈ ℝ+)

Matlab Python Ref
$\ell_0$ + conic constraints $|x|^0 + \iota_{S}(x,d)$

where

$S = \{(x,d) \in \mathbb{C}^2 \,|\, (\exists \delta \in [-\Delta, \Delta])\; d = \delta x \}$

with $\Delta \ge 0$

$\begin{cases} (0,0) & \mbox{if $|x|^2+|d|^2 < \frac{|\widehat{\delta} x - d|^2}{1+\widehat{\delta}^2}+ 2\gamma\lambda$}\\ \displaystyle \frac{x+\widehat{\delta} d}{1+\widehat{\delta}^2} (1,\widehat{\delta}) & \mbox{otherwise,} \end{cases} $

where

$\small \widehat{\delta} = \begin{cases} \min\big\{\frac{\eta+ |d|^2-|x|^2}{2|\mathrm{Re}(x d^*)|},\Delta\big\} \operatorname{sign}\big(\mathrm{Re}(x d^*)\big)& \mbox{if $\mathrm{Re}(x d^*)\neq 0$}\\ 0 & \mbox{if $\mathrm{Re}(x d^*)= 0$}\\ & \mbox{ and $|x| \ge |d|$}\\ \Delta & \mbox{otherwise,} \end{cases} $

and

$\small\eta = \sqrt{\big(|d|^2-|x|^2\big)^2+ 4 \big(\mathrm{Re}(x d^*)\big)^2}$.
[Function]
[Prox]
[ConicL0] [Florescu et al., 2013]