Gradient Descent Methods for Large-Scale Linear Inverse Problems Open Access

Abstract

Iterative gradient descent methods are frequently used for ill-posed inverse problems because they are suitable for large models and they are cheap to work with. In this thesis, we explore three dierent types of gradient descent methods: the Landweber method, method of steepest descent, and the Barzilai-Borwein method. Specically, we also compare the eciency of these methods to the conjugate gradient method. The thesis begins with an introduction to the history and application of the gradient descent methods and to the methods tested, and follows with convergence analysis and numerical experience on real images. Ways to accelerate and smooth the Barzilai-Borwein method are also included.

Table of Contents

Contents 1 Introduction 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Mathematical Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Iterative Regulizarization . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Methods 7 2.1 Gradient Descent Methods . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 The Landweber Method . . . . . . . . . . . . . . . . . . . . . 10 2.1.2 Method of Steepest Descent . . . . . . . . . . . . . . . . . . . 11 2.1.3 The Barzilai-Borwein Method . . . . . . . . . . . . . . . . . . 14 2.2 The Conjugate Gradient Method . . . . . . . . . . . . . . . . . . . . 16 3 Convergence Analysis 18 3.1 Original Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1.1 Some Background . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.2 Gradient Descent Methods . . . . . . . . . . . . . . . . . . . . 20 3.1.3 Conjugate Gradient Method . . . . . . . . . . . . . . . . . . . 22 3.2 Preconditioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4 Experiments 25 4.1 Satellite Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2 Grain Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.3 Gaussian Blur Image . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5 Conclusion and Discussion 43

About this Honors Thesis

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	Emory College
Department	Mathematics and Computer Science
Degree	BS
Submission	Honors Thesis
Language	English
Research Field	Mathematics
Keyword	Barzilai-Borwein conjugate gradient ill-posed problem gradient descent
Committee Chair / Thesis Advisor	Nagy, James, Emory University
Committee Members	Finzi, Laura, Emory University Veneziani, Alessandro, Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Gradient Descent Methods for Large-Scale Linear Inverse Problems ()	2018-08-28 11:05:58 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions