Orthant-Strictly Monotonic Norms, Generalized Top-k and k-Support Norms and the l_(0) Pseudonorm

The so-called $\ell_0$ pseudonorm on the Euclidean space $\mathbb{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$ pseudonorm) if it is nondecreasing and that the sequence of norms of a vector $x$ becomes stationary exactly at the index $\ell_0(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 $\ell_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 $\ell_0$ pseudonorm are expressed by means of the difference of two norms. Our results rely on the study of orthant-strictly monotonic norms.