Capra-Convexity, Convex Factorization and Variational Formulations for the ℓ ₀ Pseudonorm

The so-called ℓ₀ pseudonorm, or cardinality function, counts the number of nonzero components of a vector. In this paper, we analyze the ℓ₀ pseudonorm by means of so-called Capra (constant along primal rays) 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 ℓ_p-norms, but for the extreme ones). We obtain three main results. First, we show that the ℓ₀ 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 ℓ₀ pseudonorm coincides, on the unit sphere of the source norm, with a proper convex lower semicontinuous function. Third, we establish a variational formulation for the ℓ₀ pseudonorm by means of generalized top-k dual norms and k-support dual norms (that we formally introduce).