Hidden Convexity in the l₀ Pseudonorm

J.-P. Chancelier ; M. De Lara

Journal of convex analysis, Tome 28 (2021) no. 1, pp. 203-236

Résumé

The so-called l₀ pseudonorm on R^d counts the number of nonzero components of a vector. It is well-known that the l₀ pseudonorm is not convex, as its Fenchel biconjugate is zero. In this paper, we introduce a suitable conjugacy, induced by a novel coupling, ECapra, that has the property of being constant along primal rays like the l₀ pseudonorm. The coupling ECapra belongs to the class of one-sided linear couplings, that we introduce; we show that they induce conjugacies that share nice properties with the classic Fenchel conjugacy. For the ECapra conjugacy, induced by the coupling ECapra, we relate the ECapra conjugate and biconjugate of the l₀ pseudonorm, the characteristic functions of its level sets and the sequence of so-called top-k norms. In particular, we prove that the l₀ pseudonorm is equal to its biconjugate: hence, the l₀ pseudonorm is ECapra-convex in the sense of generalized convexity. As a corollary, we show that there exists a proper convex lower semicontinuous function on R^d such that this function and the l₀ pseudonorm coincide on the Euclidian unit sphere. This hidden convexity property is somewhat surprising as the l₀ pseudonorm is a highly nonconvex function of combinatorial nature. We provide different expressions for this proper convex lower semicontinuous function, and we give explicit formulas in the two-dimensional case.

Détail

Classification : 46N10, 49N15, 46B99, 52A41, 90C46
Mots-clés : l-0-pseudonorm, coupling, Fenchel-Moreau conjugacy, top-k norms, k-support norms, hidden convexity