Abstract:
In sparse optimization problems, one looks for solution that have few nonzero components.
We consider problems where sparsity is exactly measured by the l0 pseudonorm. We display a suitable conjugacy for which we show that the l0 pseudonorm is equal to its biconjugate.
As a corollary, we obtain that the (nonconvex) l0 pseudonorm coincides, on the sphere, with a convex lsc function that we characterize.
With this conjugacy, we display a lower bound for the original exact sparse optimization problem,
which is a convex minimization program over the unit ball of a so-called support norm.
Finally, we introduce generalized sparse optimization, where the solution is searched among a finite union of subsets. We provide a systematic way to design norms and lower bound convex minimization programs over their unit ball. Thus, we recover most of the sparsity-inducing norms used in machine learning.