# Instance Optimal Decoding and the Restricted Isometry Property

arXiv: https://arxiv.org/abs/1802.09905 · HTML: https://mlsanity.com/paper/1802.09905/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2018.

## Built on by (most cited first, 3 of 3)

- [Controlling Wasserstein Distances by Kernel Norms with Application to Compressive Statistical Learning](https://mlsanity.com/paper/2112.00423/) (2021)
- [Mean Nystr"om Embeddings for Adaptive Compressive Learning](https://mlsanity.com/paper/2110.10996/) (2021)
- [Asymmetric compressive learning guarantees with applications to quantized sketches](https://mlsanity.com/paper/2104.10061/) (2021)

## Abstract (arXiv)

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.