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

The so-called

pseudonorm on the Euclidean space

\mathbb{R}^d 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

\ell_0 ℓ 0

pseudonorm) if it is nondecreasing and that the sequence of norms of a vector

x x

becomes stationary exactly at the index

\ell_0(x) ℓ 0 ( x )

. In this paper, with any (source) norm, we associate sequences of generalized top-

k k

and

k k

-support norms, and we also introduce the new class of orthant-strictly monotonic norms (that encompasses the

\ell_p ℓ p

norms, but for the extreme ones). Then, we show that an orthant-strictly monotonic source norm generates a sequence of generalized top-

k 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

\ell_0 ℓ 0

pseudonorm are expressed by means of the difference of two norms. Our results rely on the study of orthant-strictly monotonic norms.