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

Abstract:

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.

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