Instance Optimal Decoding and the Restricted Isometry Property

Nicolas Keriven (1) , Rémi Gribonval (2)

1 ENS-PSL - École normale supérieure - Paris
2 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio

In this paper, we address the question of information preservation in ill-posed, non-linear inverse problems, assuming that the measured data is close to a low-dimensional model set. We provide necessary and sufficient conditions for the existence of a so-called instance optimal decoder, i.e., that is robust to noise and modelling error. Inspired by existing results in compressive sensing, our analysis is based on a (Lower) Restricted Isometry Property (LRIP), formulated in a non-linear fashion. We also provide sufficient conditions for non-uniform recovery with random measurement operators, with a new formulation of the LRIP. We finish by describing typical strategies to prove the LRIP in both linear and non-linear cases, and illustrate our results by studying the invertibility of a one-layer neural net with random weights.

Mots clés: Non-linear inverse problem; Compressed Sensing; Random features

Domaines: Théorie de l'information [cs.IT]; Apprentissage [cs.LG]

Nicolas Keriven, Rémi Gribonval. Instance Optimal Decoding and the Restricted Isometry Property. 8th International Conference on New Computational Methods for Inverse Problems (NCMIP), May 2018, Cachan, France. pp.012002, ⟨10.1088/1742-6596/1131/1/012002⟩. ⟨hal-01718411v2⟩