Inner Product Free Krylov Methods for Inverse Problems Pubblico

Abstract

Iterative Krylov projection methods have become widely used for solving large-scale linear inverse problems. Certain methods that rely on orthogonality require inner products, which create a bottleneck for parallelization and causes the algorithms to fail in low precision. As a result, there is a need for more effective iterative methods to alleviate this computational burden. This study presents new Krylov projection methods that do not require inner products to solve large-scale linear inverse problems.

The first iterative solver is known as the Changing Minimal Residual Hessenberg method (CMRH). The second is a new extension of CMRH to rectangular systems which we call the least squares LU method (LSLU). We further adapt both approaches to efficiently incorporate Tikhonov regularization. These methods are labeled as Hybrid CMRH and Hybrid LSLU. Each of these techniques are known as quasi-minimal residual methods rather than minimal residual methods. Still, these methods do not offer a way to control how closely the quasi-norm approximates the desired norm. In this work, we also propose a new Krylov method that is both inner product free and minimizes a functional that is theoretically closer to the residual norm. The new scheme combines the conventional CMRH method and the newly proposed LSLU method with a randomized sketch-and-solve technique to solve the strongly overdetermined projected least-squares problem. Extensive numerical examples illustrate the effectiveness of all methods in this dissertation.

Table of Contents

1 Introduction ............ 1

1.1 Related Work and Contributions . . . . . . . . . . . . . . . . . . . . 2

1.1.1 Inner Product Free Krylov Method . . . . . . . . . . . . . . . 3

1.1.2 Sketched Inner Product Free Methods . . . . . . . . . . . . . 3

1.2 Overview of Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Background ..............5

2.1 Regularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.1 The Need for Regularization . . . . . . . . . . . . . . . . . . . 7

2.1.2 Iterative and Variational Regularization . . . . . . . . . . . . 7

2.1.3 Hybrid Regularization . . . . . . . . . . . . . . . . . . . . . . 8

2.2 Krylov Subspace Methods . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.1 GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.2 QMR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2.3 LSQR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Randomized Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Inner Product Free Krylov Subspaces Methods ........................ 16

3.1 The Changing Minimal Residual Hessenberg Method . . . . . . . . . 16

3.1.1 The relationship between CMRH and GMRES . . . . . . . . . 19

3.1.2 Regularizing properties of CMRH . . . . . . . . . . . . . . . . 24

3.1.2.1 Singular Value Decomposition Analysis . . . . . . . . 25

3.1.2.2 Spectral Filtering Properties . . . . . . . . . . . . . . 28

3.2 Least Squares with LU Factorization . . . . . . . . . . . . . . . . . . 30

3.2.1 Extension of the Hessenberg Process . . . . . . . . . . . . . . 31

3.2.2 Theoretical bounds for the residual norm of LSLU . . . . . . . 38

3.3 Hybrid CMRH and Hybrid LSLU . . . . . . . . . . . . . . . . . . . . 41

3.3.1 Theoretical bounds for the residual norms of Hybrid CMRH and Hybrid LSLU . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.3.1.1 Residual Norm of Hybrid CMRH . . . . . . . . . . . 44

3.3.1.2 Residual Norm of Hybrid LSLU . . . . . . . . . . . . 45

3.3.2 Computational Considerations . . . . . . . . . . . . . . . . . . 48

3.3.2.1 Selecting Regularization Parameters . . . . . . . . . 48

3.3.2.2 Stopping Criterion . . . . . . . . . . . . . . . . . . . 51

3.4 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.4.1 Comparison with other inner product free methods . . . . . . 54

3.4.2 Results on low precision arithmetic . . . . . . . . . . . . . . . 56

3.4.3 Results on deblurring test problems. . . . . . . . . . . . . . . 57

3.4.4 Results on seismic test problem . . . . . . . . . . . . . . . . . 59

3.4.5 Results on different tomography test problems . . . . . . . . . 61

4 Sketched Inner Product Free Krylov Methods ................... 68

4.1 sCMRH and sLSLU . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4.2 Extensions for Tikhonov Regularization . . . . . . . . . . . . . . . . . 73

4.3 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

4.3.1 Deblurring problem . . . . . . . . . . . . . . . . . . . . . . . . 77

4.3.2 Neutron tomography simulation . . . . . . . . . . . . . . . . . 77

4.3.3 Real data examples . . . . . . . . . . . . . . . . . . . . . . . . 80

5 Conclusion .......................................... 85

Bibliography ................................... 87

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Mathematics
Degree	Ph.D.
Submission	Dissertation
Language	English
Research Field	Mathematics
Parola chiave	inner product free methods sketching Krylov subspace methods Tikhonov regularization randomized inverse problems
Committee Chair / Thesis Advisor	James Nagy, Emory University
Committee Members	Malena Sabaté Landman, University of Oxford Julianne Chung, Emory University Talea Mayo, Emory University

Ultima modifica

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Inner Product Free Krylov Methods for Inverse Problems ()	2025-04-04 16:25:30 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions