  Methods inspired by Artificial Intelligence (AI) are starting to
fundamentally change computational science and engineering through breakthrough
performances on challenging problems. However, reliability and trustworthiness
of such techniques is a major concern. In inverse problems in imaging, the
focus of this paper, there is increasing empirical evidence that methods may
suffer from hallucinations, i.e., false, but realistic-looking artifacts;
instability, i.e., sensitivity to perturbations in the data; and unpredictable
generalization, i.e., excellent performance on some images, but significant
deterioration on others. This paper provides a theoretical foundation for these
phenomena. We give mathematical explanations for how and when such effects
arise in arbitrary reconstruction methods, with several of our results taking
the form of `no free lunch' theorems. Specifically, we show that (i) methods
that overperform on a single image can wrongly transfer details from one image
to another, creating a hallucination, (ii) methods that overperform on two or
more images can hallucinate or be unstable, (iii) optimizing the
accuracy-stability trade-off is generally difficult, (iv) hallucinations and
instabilities, if they occur, are not rare events, and may be encouraged by
standard training, (v) it may be impossible to construct optimal reconstruction
maps for certain problems. Our results trace these effects to the kernel of the
forward operator whenever it is nontrivial, but also apply to the case when the
forward operator is ill-conditioned. Based on these insights, our work aims to
spur research into new ways to develop robust and reliable AI-based methods for
inverse problems in imaging.
