  We propose a new class of exact continuous relaxations of l0-regularized
criteria involving non-quadratic data terms such as the Kullback-Leibler
divergence and the logistic regression, possibly combined with an l2
regularization. We first prove the existence of global minimizers for such
problems and characterize their local minimizers.Then, we propose the l0
Bregman Relaxation (B-rex), a continuous approximation of the l0 pseudo-norm
defined in terms of suitable Bregman distances, which leads to an exact
continuous relaxations of the original l0-regularized problem in the sense that
it does not alter its set of global minimizers and reduces the non-convexity by
eliminating certain local minimizers. Both features make the relaxed problem
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.
