pyproximal.QuadraticEnvelopeCardIndicator#

class pyproximal.QuadraticEnvelopeCardIndicator(r0)[source]#

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 [3] for details. There are other, equivalent ways, of expressing this penalty, see e.g. [1] and [2].

Parameters
r0int

Threshold parameter.

See also

QuadraticEnvelopeCard

Quadratic envelope of the \(\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 indicator function of the cardinality function, such expressions do exist.

The proximal operator does not have a closed-form, and we refer to [1] 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)