Safe squeezing for antisparse coding

Clément Elvira (PANAMA research group, Iniria, CNRS, IRISA - Rennes)
October 04, 2019 — 14:00 — "None"

Abstract

Spreading the information over all coefficients of a representation is a desirable property in many applications such as digital communication or machine learning. This so-called antisparse representation can be obtained by solving a convex program involving a $\ell_\infty$-norm penalty combined with a quadratic discrepancy. In this talk, we propose a new methodology, dubbed safe squeezing, to accelerate the computation of antisparse representation. We describe a test that allows to detect saturated entries in the solution of the optimization problem. The contribution of these entries is compacted into a single vector, resulting in a form of dimensionality reduction. We propose two algorithms to solve the latter lower dimensional problem. Numerical experiments show both the effectiveness of the saturation detection tests and that the proposed procedures lead to significant computational gains as compared to existing methods.

Biography

Clément Elvira is a postdoctoral researcher at Inria Rennes - Bretagne atlantique and part of the BECOSE project. He is working under the supervision of Cédric Herzet, Rémi Gribonval and Charles Soussen. He was a PhD student from october, 2014 to november, 2017 at CRIStAL in Lille, France, under the supervision of Pierre Chainais and Nicolas Dobigeon, and he was part of the SigMA group at CRIStAL.