On the sample complexity of inverse problems

Giovanni Alberti (University of Genoa, Italy)

Many inverse problems are modelled by integral or partial differential equations, including, for instance, the inversion of the Radon transform in computed tomography and the Calderón problem in electrical impedance tomography. As such, these inverse problems are intrinsically infinite dimensional and, in theory, require infinitely many measurements for the reconstruction. In this talk, I will discuss recovery guarantees with finite measurements, and with explicitly estimates on the sample complexity, namely, on the number of measurements. These results use methods of sampling theory and compressed sensing, and work under the assumption that the unknown either belongs to a finite-dimensional subspace/submanifold or enjoys sparsity properties. I will consider both linear problems, such as the sparse Radon transform, and nonlinear problems, such as the Calderón problem and inverse scattering.

A similar issue arises when applying machine learning methods for solving inverse problems, as for instance to learn the regularizer, which may depend on infinitely many parameters. I will present sample complexity results on the size of the training set, both in the case of generalized Tychonov regularization, and with $\ell^1$-type penalties.

This talk is based on a series of joint works with Á. Arroyo, P. Campodonico, E. De Vito, A. Felisi, T. Helin, M. Lassas, L. Ratti, M. Santacesaria, S. Sciutto and S. I. Trapasso.