Journal of Convex Analysis 30 (2023), No. 3, 743--769
Copyright Heldermann Verlag 2023
Orthant-Strictly Monotonic Norms, Generalized Top-k and k-Support Norms and the l0 Pseudonorm
Jean-Philippe Chancelier
CERMICS, Ecole des Ponts, Marne-la-Vallée, France
jean-philippe.chancelier@enpc.fr
Michel De Lara
CERMICS, École des Ponts, Marne-la-Vallée, France, Marne-la-Vallée, France
michel.delara@enpc.fr
[Abstract-pdf]
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.
Keywords: $\ell_0$ pseudonorm, orthant-strictly monotonic norm, generalized top-$k$ norm, generalized $k$-support norm, strictly graded sequence of norms.
MSC: 15A60, 46N10.
[ Fulltext-pdf (202 KB)] for subscribers only.