On $\ell_{0}$ Bregman-Relaxations for Kullback-Leibler Sparse Regression

The resolution of optimization problems involving the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{0}$</tex> pseudo-norm has proven to be of importance in signal processing and ma-chine learning applications for selecting relevant variables. Among the vast class of existing approaches dealing with the intrinsic NP-hardness of such problems, continuous (possibly non-convex) re-laxations have been increasingly considered over the recent years. The notion of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{0}$</tex> -Bregman relaxation (B-rex) has been recently in-troduced to construct effective relaxations of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{0}$</tex> -regularized objectives with general data terms. These relaxations are termed exact in the sense that they preserve the global minimizers while removing some local minimizers. In this study, we deepen this idea further for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{0}$</tex> -regularized Kullback-Leibler regression problems, designing a tailored B-rex. Compared to other relaxations, it further reduces the number of local minimizers of the original problem by means of a suitable analytical/geometrical modeling. To better exploit the geometry of the relaxed problem, we deploy a dedicated Bregman proximal gradient algorithm for its minimization.