A framework for optimal convex regularization for the recovery of low-dimensional models
Yann Traonmilin  1  , Rémi Gribonval  2  , Samuel Vaiter  3  
1 : Univ. Bordeaux, Bordeaux INP, CNRS, IMB, UMR 5251,F-33400 Talence
CNRS : UMR5251
2 : Univ Lyon, ENS de Lyon, UCBL, CNRS, Inria, LIP, F-69342 Lyon,
L'Institut National de Recherche en Informatique et e n Automatique (INRIA)
3 : CNRS, Université Côte d'Azur, LJAD, Nice, France
CNRS : UMR7351

We consider the problem of recovering elements of a low-dimensional model from under-determined linear measurements. To perform recovery, we consider the minimization of a convex regularizer subject to a data fit constraint. Given a model, we ask ourselves what is the "best" convex regularizer to perform its recovery. To answer this question, we define an optimal regularizer as a function that maximizes a compliance measure with respect to the model. We introduce and study several notions of compliance. We give analytical expressions for compliance measures based on the best-known recovery guarantees with the restricted isometry property. These expressions permit to show the optimality of the ℓ1-norm for sparse recovery and of the nuclear norm for low-rank matrix recovery for these compliance measures. We also investigate the construction of an optimal convex regularizer using the example of sparsity in levels.

Personnes connectées : 3 Vie privée