The Capra-subdifferential of the ℓ₀ pseudonorm

Abstract

The ${\ell }_0$ pseudonorm counts the nonzero coordinates of a vector. It is often used in optimization problems to enforce the sparsity of the solution. However, this function is nonconvex and noncontinuous, and optimization problems formulated with ${\ell }_0$ – be it in the objective function or in the constraints – are hard to solve in general. Recently, a new family of coupling functions – called Capra (constant along primal rays) – has proved to induce relevant generalized Fenchel-Moreau conjugacies to handle the ${\ell }_0$ pseudonorm. In particular, under a suitable choice of source norm on ${\mathbb{R}}^d$ – used in the definition of the Capra coupling – the function ${\ell }_0$ is Capra-subdifferentiable, hence is Capra-convex. In this article, we give explicit formulations for the Capra-subdifferential of the ${\ell }_0$ pseudonorm, when the source norm is a ${\ell }_p$ norm with $p\in [1,\mathrm{\infty }]$. We illustrate our results with graphical visualizations of the Capra-subdifferential of ${\ell }_0$ for the Euclidean source norm.

Keywords:

• Generalized subdifferential
• ${\ell }_0$ pseudonorm
• sparsity
• Capra-coupling

Acknowledgements

We thank the two anonymous referees that helped us to improve the quality of this paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 Here, following notation from Game Theory, we have denoted by $-K$ the complementary subset of K in $\{1,\dots ,d\}$: $K\cup (-K)=\{1,\dots ,d\}$ and $K\cap (-K)=\mathrm{\varnothing }$.