Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01wp988j85k
Title: Regularization of Linear Systems with Sparsity Constraints with Applications to Large Scale Inverse Problems
Authors: Voronin, Sergey
Advisors: Daubechies, Ingrid
Contributors: Applied and Computational Mathematics Department
Keywords: geotomography
inverse problem
iterative method
regularization
sparsity
Subjects: Applied mathematics
Issue Date: 2012
Publisher: Princeton, NJ : Princeton University
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.
URI: http://arks.princeton.edu/ark:/88435/dsp01wp988j85k
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Applied and Computational Mathematics

Files in This Item:
File Description SizeFormat 
Voronin_princeton_0181D_10435.pdf5.64 MBAdobe PDFView/Download


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.