Sampling rates for l1 synthesis

Claire Boyer (Sorbonne Université)
March 05, 2021 — 11:00 — Online

Abstract

This work investigates the problem of signal recovery from undersampled noisy sub-Gaussian measurements under the assumption of a synthesis-based sparsity model. Solving the l1-synthesis basis pursuit allows to simultaneously estimate a coefficient representation as well as the sought-for signal. However, due to linear dependencies within redundant dictionary atoms it might be impossible to identify a specific representation vector, although the actual signal is still successfully recovered. We study both estimation problems from a non-uniform, signal-dependent perspective. By utilizing results from linear inverse problems and convex geometry, we identify the sampling rate describing the phase transition of both formulations, and propose a “tight” estimated upper-bound. This is a joint work with Maximilian März (TU Berlin), Jonas Kahn and Pierre Weiss (CNRS, Toulouse).

References

M. März, C. Boyer, J. Kahn, and P. Weiss, “Sampling Rates for $\ell^1$-Synthesis,” arXiv:2004.07175 [cs, math], Apr. 2020, 2021. [Online]. Available: http://arxiv.org/abs/2004.07175.

Biography

Claire Boyer est maîtresse de conférences à Sorbonne Université depuis 2016, et a été membre associé au Département de Mathématiques et Applications à l’ENS Ulm de 2017 à 2020. Ses domaines de recherche sont au carrefour du compressed sensing, des statistiques de grande dimension, de l’optimisation, des problèmes inverses et du machine learning. Durant les 4 dernières années, elle a principalement consacré ses travaux de recherche à la reconstruction d’objets à partir d’un faible nombre d’observations linéaires, faible devant la dimension de l’objet à reconstruire. L’objet d’intérêt pouvait aussi bien être un vecteur en dimension finie (on parle alors de compressed sensing), qu’une matrice avec entrées manquantes (on parle alors de complétion de matrice), qu’une mesure de Radon (on parle alors de “compressed sensing off-the- grid”). Plus récemment, elle s’est aussi intéressée aux problèmes d’apprentissage statistique lorsque les données peuvent être manquantes.