Orthant-Strictly Monotonic Norms, Graded Sequences and Generalized Top-k and k-Support Norms for Sparse Optimization

The so-called l0 pseudonorm on Rd counts the number of nonzero components of a vector. We say that a sequence of norms on Rd is strictly increasingly graded (with respect to the l0 pseudonorm) if it is nondecreasing and that the sequence of norms of a vector x becomes stationary exactly at the index l0(x). In the same way, we define strictly decreasingly graded sequences. Thus, a strictly graded sequence detects the number of nonzero components of a vector in Rd in such a way that the level sets of the l0 pseudonorm can be expressed by means of the difference of two convex functions (norms). We also introduce sequences of generalized top-k and k-support norms, generated from any (source) norm on Rd, and the class of orthant-strictly monotonic norms on Rd. Then, we show how these three new notions prove especially relevant for the l0 pseudonorm. Indeed, on the one hand, we show that an orthant-strictly monotonic source norm generates a sequence of generalized top-k norms which is strictly increasingly graded with respect to the l0 pseudonorm. On the other hand, we show that a source norm, which is orthant-monotonic and which makes the normed space Rd strictly convex when equipped with it, generates a sequence of generalized k-support norms that is strictly decreasingly graded. Thus, we provide a systematic way to generate sequences of norms with which we can express the level sets of the l0 pseudonorm by means of the difference of two norms