Orthant-Strictly Monotonic Norms, Generalized Top-k and k-Support Norms and the ℓ₀ Pseudonorm

The so-called ℓ₀ pseudonorm on the Euclidean space R^d counts the number of nonzero components of a vector. We say that a sequence of norms is strictly increasingly graded (with respect to the ℓ₀ pseudonorm) if it is nondecreasing and that the sequence of norms of a vector x becomes stationary exactly at the index ℓ₀(x). In this paper, with any (source) norm, we associate sequences of generalized top-k and k-support norms, and we also introduce the new class of orthant-strictly monotonic norms (that encompasses the ℓ_p norms, but for the extreme ones). Then, we show that an orthant-strictly monotonic source norm generates a sequence of generalized top-k norms which is strictly increasingly graded. With this, we provide a systematic way to generate sequences of norms with which the level sets of the ℓ₀ pseudonorm are expressed by means of the difference of two norms. Our results rely on the study of orthant-strictly monotonic norms.