pyproximal.QuadraticEnvelopeCard

class pyproximal.QuadraticEnvelopeCard(mu)

Quadratic envelope of the \(\ell_0\)-penalty.

The \(\ell_0\)-penalty is also known as the cardinality function, and the quadratic envelope \(\mathcal{Q}(\mu\|\cdot\|_0)\) of it is defined as

\[\mathcal{Q}(\mu\|\cdot\|_0)(x) = \sum_i \left(\mu - \frac{1}{2}\max(0, \sqrt{2\mu} - |x_i|)^2\right)\]

where \(\mu \geq 0\).

Parameters

mufloat

Threshold parameter.

See also

QuadraticEnvelopeCardIndicator

Quadratic envelope of the indicator function of \(\ell_0\)-penalty

Notes

The terminology quadratic envelope was coined in [1], however, the rationale has been used earlier, e.g. in [2]. In a general setting, the quadratic envelope \(\mathcal{Q}(f)(x)\) is defined such that

\[\left(f(x) + \frac{1}{2}\|x-y\|_2^2\right)^{**} = \mathcal{Q}(f)(x) + \frac{1}{2}\|x-y\|_2^2\]

where \(g^{**}\) denotes the bi-conjugate of \(g\), which is the l.s.c. convex envelope of \(g\).

There is no closed-form expression for \(\mathcal{Q}(f)(x)\) given an arbitrary function \(f\). However, for certain special cases, such as in the case of the cardinality function, such expressions do exist.

The proximal operator is given by

\[\begin{split}\prox_{\tau\mathcal{Q}(\mu\|\cdot\|_0)}(x) = \begin{cases} x_i, & |x_i| \geq \sqrt{2 \mu} \\ \frac{x_i-\tau\sqrt{2\mu}\sgn(x_i)}{1-\tau}, & \tau\sqrt{2\mu} < |x_i| < \sqrt{2 \mu} \\ 0, & |x_i| \leq \tau\sqrt{2 \mu} \end{cases}\end{split}\]

By inspecting the structure of the proximal operator it is clear that large values are unaffected, whereas smaller ones are penalized partially or completely. Such properties are desirable to counter the effect of shrinking bias observed with e.g. the \(\ell_1\)-penalty. Note that in the limit \(\tau=1\) this becomes the hard thresholding with threshold \(\sqrt{2\mu}\). It should also be noted that this proximal operator is identical to the Minimax Concave Penalty (MCP) proposed in [3].

References

1

Carlsson, M. “On Convex Envelopes and Regularization of Non-convex Functionals Without Moving Global Minima”, In Journal of Optimization Theory and Applications, 183:66–84, 2019.

2

Larsson, V. and Olsson, C. “Convex Low Rank Approximation”, In International Journal of Computer Vision (IJCV), 120:194–214, 2016.

3

Zhang et al. “Nearly unbiased variable selection under minimax concave penalty”, In the Annals of Statistics, 38(2):894–942, 2010.

Methods

__init__(mu)
affine_addition(v)	Affine addition
chain(g)	Chain
elementwise(x)
grad(x)	Compute gradient
postcomposition(sigma)	Postcomposition
precomposition(a, b)	Precomposition
prox(**kwargs)
proxdual(**kwargs)

Examples using pyproximal.QuadraticEnvelopeCard

Concave penalties

Concave penalties