Exact continuous relaxations of $$\ell _0$$ ℓ 0 -regularized criteria with non-quadratic data terms

We consider the minimization of $$\ell _0$$ ℓ 0 -regularized criteria involving non-quadratic data terms such as the Kullback-Leibler divergence and the logistic regression, possibly combined with an $$\ell _2$$ ℓ 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$$ ℓ 0 pseudo-norm, termed as $$\ell _0$$ ℓ 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$$ ℓ 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.