8th International Conference on
Computational Harmonic Analysis

September 12-16, 2022

Ingolstadt, Germany

"Sample complexity of ill-posed inverse problems via compressed sensing"

Felisi, Alessandro

Compressed sensing (CS) is one of the most thriving branches of applied mathematics in recent years, focusing on the recovery of sparse signals, which actually constitute the most abundant species in real-world scenarios. The theoretical and algorithmic frameworks of CS are currently well understood for finite-dimensional vector spaces. Nevertheless, models arising from inverse problems for PDEs have inherently infinite-dimensional features, as they typically involve operators between Hilbert spaces or the reconstruction of a function from a finite number of pointwise samples. We move the first steps towards a unified framework for the study of the sample complexity of several classes of ill-posed inverse problems, hence enforcing stable reconstruction of input signals (or suitable finite-dimensional approximations) from a finite number of noisy samples of its images. Our general framework encompasses both the case where the measurements are inner products with elements of a certain dictionary as well as the interpolation scenario where pointwise samples of a function are taken into account. We prove uniform recovery guarantees for bounded operators satisfying weak regularity assumptions (such as restricted injectivity or approximate diagonalization) which happen to be satisfied by many of the relevant operators in inverse problems.

« back