  In exact sparse optimization problems on Rd (also known as sparsity
constrained problems), one looks for solution that have few nonzero components.
In this paper, we consider problems where sparsity is exactly measured either
by the nonconvex l0 pseudonorm (and not by substitute penalty terms) or by the
belonging of the solution to a finite union of subsets. Due to the
combinatorial nature of the sparsity constraint, such problems do not generally
display convexity properties, even if the criterion to minimize is convex. In
the most common approach to tackle them, one replaces the sparsity constraint
by a convex penalty term, supposed to induce sparsity. Thus doing, one loses
the original exact sparse optimization problem, but gains convexity. However,
by doing so, it is not clear that one obtains a lower bound of the original
exact sparse optimization problem. In this paper, we propose another approach,
where we lose convexity but where we gain at keeping the original exact sparse
optimization formulation, by displaying lower bound convex minimization
programs. For this purpose , we introduce suitable conjugacies, induced by a
novel class of one-sided linear couplings. Thus equipped, we present a
systematic way to design norms and lower bound convex minimization programs
over their unit ball. The family of norms that we display encompasses most of
the sparsity inducing norms used in machine learning. Therefore, our approach
provides foundation and interpretation for their use.
