Hidden Convexity in the l0 Pseudonorm

The so-called l0 pseudonorm on R d counts the number of nonzero components of a vector. It is well-known that the l0 pseudonorm is not convex, as its Fenchel biconjugate is zero. In this paper, we introduce a suitable conjugacy, induced by a novel coupling, Caprac, having the property of being constant along primal rays, like the l0 pseudonorm. The coupling Caprac belongs to the class of one-sided linear couplings, that we introduce. We show that they induce conjugacies that share nice properties with the classic Fenchel conjugacy. For the Caprac conjugacy, induced by the coupling Caprac, we prove that the l0 pseudonorm is equal to its biconjugate: hence, the l0 pseudonorm is Caprac-convex in the sense of generalized convexity. We also provide expressions for conjugates in terms of two families of dual norms, the 2-k-symmetric gauge norms and the k-support norms. As a corollary, we show that the l0 pseudonorm coincides, on the sphere, with a proper convex lower semicontinuous function-that we characterize, and for which we give explicit formulas in the two dimensional case. This is somewhat surprising as the l0 pseudonorm is a highly nonconvex function of combinatorial nature