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.$ $\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]

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]