Regularization of Linear Systems with Sparsity Constraints with Applications to Large Scale Inverse Problems

Abstract

This thesis is about numerical methods for the regularization of large scale inverse problems

with sparsity constraints. Some new methods are proposed, and applied to an inverse problem from Geotomography, the goal of which is to determine latitudinal and longitudinal corrections

to a spherically symmetric wave velocity model of the Earth's interior.

The problem involves a very large, badly conditioned linear system, whose solutions,

expressed in an intricate coordinate system, can be sparsely represented under the action of a

wavelet transformation. The methods we develop and analyze in this thesis are simple to implement, efficient and easy to parallelize on large machines. In addition, the convergence analysis for the new algorithms assumes minimal conditions on the linear systems they are applied to.

This thesis is organized as follows. After the introduction, we give in Chapter 2, an overview of

existing schemes for regularization with sparsity constraints, and we introduce new material developed in the remainder of the thesis. Chapter 3 introduces a new firm thresholding based scheme that overcomes some shortcomings of soft thresholding;

this scheme applies less penalty to the large

coefficients of the iterates, while producing solutions of comparable sparsity. Chapter 4 introduces

two novel methods based on an iteratively reweighted least squares strategy. These methods are designed to minimize a new more general sparsity promoting functional, which is especially useful for structured sparse problems, such as those encountered under the action of a wavelet transform. Detailed convergence analysis is provided for these two new algorithms. Chapter 5 discusses techniques that are useful for numerical implementation, such as a fast implementation of a randomized low rank SVD approximation and matrix column norm estimations, useful for large badly conditioned matrices. Finally, Chapter 6 presents the application, collecting ideas from the previous chapters and applying them to the inverse problem.