Repository logo

On the Foundations of Computation and Sampling for Reconstruction and Approximation



Change log



These days we use numerical methods in a large variety of applications. Many of them are security sensitive, like image reconstruction and classification in health care or scene detection for self-driving cars. In these cases, it is of utmost importance that we can guarantee that the algorithms work stably and accurately. To ensure this we investigate the foundations of computability and the numerical behaviour of the following methods. These are the linear reconstruction methods: generalized sampling and the parametrized background data weak (PBDW)-method. Moreover, we also analyse their non-linear cousin structured compressed sensing (CS). Finally, we consider deep learning with neural networks, which differs to the ones before in terms that it is data-based in contrast to model-based. For the model-based reconstruction methods we focus on their numerical behaviour and the optimal sampling such that we can reduce the number of costly samples and keep the desired accuracy. We investigate the case of binary measurements and wavelet reconstruction. We show that for the linear methods a linear relationship between the number of samples and coefficients is sufficient to guarantee a stable and accurate reconstruction. For structured CS we give sufficient conditions on the sampling pattern for non-uniform recovery guarantees. In the setting of data-based methods, the numerical experiments and the usage in practice suggest that the learned approximation is not stable and hence the algorithm does not give an accurate result. We investigate this problem with further numerical experiments to highlight the fundamental difficulty of explaining this phenomenon. In a second step we introduce a framework to understand the computability of learning from point samples with finite precision. In the future we aim to extend this work to give a guideline on the stable usage of deep learning with neural networks.





Hansen, Anders Christian


Inverse Propblems, Reconstruction guarantees, Walsh, Wavelets, Deep Learning, Computability


Doctor of Philosophy (PhD)

Awarding Institution

University of Cambridge
EPSRC (1804234)