Hidden Convexity in the l0 Pseudonorm and in Sparse Optimization

Michel de Lara (CERMICS, École des Ponts ParisTech)

Lundi 22 avril, 11h00, salle Coriolis (Galois).

Abstract. The so-called l0 pseudonorm counts the number of nonzero entries of a vector. As a function, it is piecewise constant. However, we show that the l0 pseudonorm displays hidden convexity and we discuss possible applications in sparse optimization.

The talk is organized in three parts.

First, we provide background on so-called couplings and Fenchel-Moreau conjugates. In generalized convexity, the duality product is replaced by a coupling c, the Fenchel conjugacy by the c-conjugacy associated with the coupling c, closed convex functions by c-convex functions (functions that are equal to their c-biconjugates), and subdifferentials by c-subdifferentials.

Second, we review (surprising) results about the l0 pseudonorm. We present the E-Capra coupling, derived from the Euclidean norm, and we show that the l0 pseudonorm is E-Capra-convex. We deduce that l0 coincides, on the unit sphere, with a proper convex lsc function — that we call the l0-cup and that we describe. Then, we go beyond the Euclidean norm, and we outline the role of orthant-strictly monotonous norms.

Third, we discuss possible applications in sparse optimization:
Fermat rule, Capra-cuts method and sparsity-inducing norms.

(Joint work with Jean-Philippe Chancelier)