Nonconvex functions

Scalar variable - Vector variable - Complex variable

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]
(coming soon) [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]
(coming soon) [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]
(coming soon)
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]
(coming soon)
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-1) t^{q-1} + t-1 = 0$
[Function]
[Prox]
(coming soon) [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]
(coming soon) [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]
(coming soon) [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]
(coming soon) [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]
(coming soon) [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]
(coming soon) [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]
(coming soon) [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]
(coming soon) [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]
(coming soon) [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]
(coming soon) [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]
(coming soon) [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]
(coming soon) [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]
(coming soon) [Florescu et al., 2013]