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

Abstract We consider the minimization of $$\ell _0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:math> -regularized criteria involving non-quadratic data terms such as the Kullback-Leibler divergence and the logistic regression, possibly combined with an $$\ell _2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:math> pseudo-norm, termed as $$\ell _0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:math> Bregman Relaxations (B-rex). They are defined in terms of suitable Bregman distances and lead to exact continuous relaxations of the original $$\ell _0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:math> -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.