Hidden Convexity in the l₀ Pseudonorm

The so-called ℓ₀ pseudonorm on ℝ^d counts the number of nonzero components of a vector. It is well-known that the ℓ₀ pseudonorm is not convex, as its Fenchel biconjugate is zero. In this paper, we introduce a suitable conjugacy, induced by a novel coupling, E-Capra, that has the property of being constant along primal rays like the ℓ₀ pseudonorm. The coupling E-Capra 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 E-Capra conjugacy, induced by the coupling E-Capra, we relate the E-Capra conjugate and biconjugate of the ℓ₀ pseudonorm, the characteristic functions of its level sets and the sequence of so-called top-k norms. In particular, we prove that the ℓ₀ pseudonorm is equal to its biconjugate: hence, the ℓ₀ pseudonorm is E-Capra-convex in the sense of generalized convexity. As a corollary, we show that there exists a proper convex lower semicontinuous function on ℝ^d such that this function and the ℓ₀ pseudonorm coincide on the Euclidean unit sphere. This hidden convexity property is somewhat surprising as the ℓ₀ pseudonorm is a highly nonconvex function of combinatorial nature. We provide different expressions for this proper convex lower semicontinuous function, and we give explicit formulas in the two-dimensional case.