Hidden Convexity in the l0 Pseudonorm and Lower Bound Convex Programs for Exact Sparse Optimization




In sparse optimization problems, one looks for solution that have few nonzero components.

We consider problems where sparsity is exactly measured by the l0 pseudonorm. We display a suitable conjugacy for which we show that the l0 pseudonorm is equal to its biconjugate.

As a corollary, we obtain that the (nonconvex) l0 pseudonorm coincides, on the sphere, with a convex lsc function that we characterize.


With this conjugacy, we display a lower bound for the original exact sparse optimization problem,

which is a convex minimization program over the unit ball of a so-called support norm.


Finally, we introduce generalized sparse optimization, where the solution is searched among a finite union of subsets. We provide a systematic way to design norms and lower bound convex minimization programs over their unit ball. Thus, we recover most of the sparsity-inducing norms used in machine learning.

Date: Jun 19, 2019 at 16:00:00 h
Venue: Beauchef 851, Torre Norte, Piso 7, Sala de Seminarios John Von Neumann CMM.
Speaker: Michel De Lara
Affiliation: Ecole des Ponts ParisTech
Coordinator: Prof. Juan Peypouquet

Posted on Apr 30, 2019 in Optimization and Equilibrium, Seminars