On the existence of optimal set-valued decoders and their accuracy bounds for ill-posed inverse problems

Abstract Ill-posed inverse problems occur everywhere in the sciences, including medical imaging, radar, astronomy, etc., yielding underdetermined or ill-posed linear (non-linear) reconstruction problems. There are now a myriad of techniques to design decoders/reconstruction methods that can tackle such problems, ranging from optimisation-based approaches, such as compressed sensing, to data-driven techniques such as deep learning (DL) and variants in between the two techniques. The variety of methods begs for a unifying approach to determine the existence of optimal decoders and fundamental accuracy bounds in order to facilitate a theoretical and empirical understanding of the performance of existing and future methods. Such a theory must allow for both single-valued and set-valued decoders, as underdetermined and ill-posed inverse problems typically have multiple solutions. Indeed, set-valued decoders arise due to non-uniqueness of minimisers in optimisation problems, such as in compressed sensing, and for DL-based decoders in generative adversarial models, such as diffusion models and ensemble models. In this work, we provide a framework for assessing the lowest possible reconstruction accuracy in terms of worst-case and average errors. The universal bounds only depend on the measurement model upper F F $F$ , the model class script upper M 1 M 1 $\\mathscr{M}_1$ and the noise model script upper E E $\\mathscr{E}$ . For linear upper F F $F$ , these bounds depend on its kernel, and in the non-linear case, the concept of kernel is generalised for undersampled and ill-posed settings. Additionally, we provide set-valued variational solutions that obtain the lowest possible reconstruction error.