We consider the minimization of \(\ell _0\) -regularized criteria involving non-quadratic data terms such as the Kullback-Leibler divergence and the logistic regression, possibly combined with an \(\ell _2\) regularization. We first prove the existence of global minimizers for such problems and characterize their local minimizers. Then, we propose a new class of continuous relaxations of the \(\ell _0\) pseudo-norm, termed as \(\ell _0\) Bregman Relaxations (B-rex). They are defined in terms of suitable Bregman distances and lead to exact continuous relaxations of the original \(\ell _0\) -regularized problem in the sense that they do not alter its set of global minimizers and reduce its non-convexity by eliminating certain local minimizers. Both features make such relaxed problems more amenable to be solved by standard non-convex optimization algorithms. In this spirit, we consider the proximal gradient algorithm and provide explicit computation of proximal points for the B-rex penalty in several cases. Finally, we report a set of numerical results illustrating the geometrical behavior of the proposed B-rex penalty for different choices of the underlying Bregman distance, its relation with convex envelopes, as well as its exact relaxation properties in 1D/2D and higher dimensions.
