Quadratic envelope of the indicator function of the $$\ell_0$$-penalty.

The $$\ell_0$$-penalty is also known as the cardinality function, and the indicator function $$\mathcal{I}_{r_0}$$ is defined as

$\begin{split}\mathcal{I}_{r_0}(\mathbf{x}) = \begin{cases} 0, & \mathbf{x}\leq r_0 \\ \infty, & \text{otherwise} \end{cases}\end{split}$

Let $$\tilde{\mathbf{x}}$$ denote the vector $$\mathbf{x}$$ resorted such that the sequence $$(\tilde{x}_i)$$ is non-increasing. The quadratic envelope $$\mathcal{Q}(\mathcal{I}_{r_0})$$ can then be written as

$\mathcal{Q}(\mathcal{I}_{r_0})(x) = \frac{1}{2k^*}\left(\sum_{i>r_0-k^*}|\tilde{x}_i|\right)^2 - \frac{1}{2}\left(\sum_{i>r_0-k^*}|\tilde{x}_i|\right)^2$

where $$r_0 \geq 0$$ and $$k^* \leq r_0$$, see  for details. There are other, equivalent ways, of expressing this penalty, see e.g.  and .

Parameters
r0int

Threshold parameter.

QuadraticEnvelopeCard

Quadratic envelope of the $$\ell_0$$-penalty

Notes

The terminology quadratic envelope was coined in , however, the rationale has been used earlier, e.g. in . 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 indicator function of the cardinality function, such expressions do exist.

The proximal operator does not have a closed-form, and we refer to  for more details. Note that this is a non-separable penalty.

References

1(1,2,3)

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(1,2)

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

3

Andersson et al. “Convex envelopes for fixed rank approximation”, In Optimization Letters, 11:1783–1795, 2017.

Methods

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