Capra-Convexity, Convex Factorization and Variational Formulations for the l0 Pseudonorm.

The so-called l0 pseudonorm on the Euclidean space Rd counts the number of nonzero components of a vector. In this paper, we analyze the l0 pseudonorm by means of so-called Capra conjugacies, for which the underlying source norm and its dual norm are both orthant-strictly monotonic (a notion that we formally introduce and that encompasses the lp norms, but for the extreme ones). We obtain three main results. First, we show that the l0 pseudonorm is equal to its Capra-biconjugate, that is, is a Capra-convex function. Second, we deduce an unexpected consequence, that we call convex factorization: the l0 pseudonorm coincides, on the unit sphere of the source norm, with a proper convex lower semicontinuous function. Third, we establish variational formulations for the l0 pseudonorm by means of generalized top-k dual~norms and k-support dual~norms (that we formally introduce).