Probabilistic Approximations of Matrix Decompositions for Inverse Problems

Abstract

Inverse problems arise in a wide range of subjects, such as medicine , cosmology, and engineering.These problems are often high dimensional, making them difficult to analyse and solve, particularly in industrial applications where timeframes are narrow. The aim of this thesis is to provide broadly applicable methods to reduce the computational costs involved in inverse problems. I consider solving inverse problems in two stages. The first is the offline phase. This is the stage of modelling and analysing the problem. This is sometimes called the “laboratory” or “research” stage. The second stage is online, where real data is coming in and a corresponding solution is found. Typically, the offline stage requires and can access greater computational resources than the online stage. Methods of reducing computational costs at the offline and online stage are presented in this thesis. This thesis primarily takes the Bayesian viewpoint of inverse problems. Much of the analysis in this thesis is of linear inverse problems with Gaussian unknowns. Such problems can be expressed in terms of linear algebra, so much of this thesis is concerned with numerical linear algebra. A particular focus is approximate matrix decompositions. This thesis makes use of the Sherman-Morrison-Woodbury formula/matrix inversion lemma, Schur Complements, pseudoinverses, the eigenvalue decomposition, the singular value decomposition, the Cholesky decomposition and particularly the QR decomposition. This thesis presents a methodology of computing the QR decomposition of sample approximations to matrices, and demonstrates applications of such factorisations to inverse problems. This thesis also makes use of probabilistic algorithms for constructing approximate matrix decompositions. A probabilistic method of constructing locally accurate matrix approximations is introduced. A particular focus of this thesis is the Bayesian approximation error framework, in which simulations are computed at the offline stage in order to reduce computational cost at the online stage. The Bayesian approximation error, sample QR factorisation, and locally accurate probabilistic approximations are combined to reduce computational costs. The methods of this thesis are demonstrated separately, typically on 1D deconvolution. These methods are then combined and applied to the linear problems of 2D deconvolution and x-ray tomography. The methods of this thesis are also applied to the nonlinear simplified conductivity imaging problem.