Efficient Preconditioner for Covariance Matrices Using Geometric Information Open Access

Luo, Qi (Spring 2022)

Permanent URL: https://etd.library.emory.edu/concern/etds/tx31qj932?locale=en
Published

Abstract

The Gaussian process is a non-parametric machine learning tool designed to solve regression

and make predictions. While the Gaussian process is very applicable in statistical modeling, in

most cases the computation remains expensive because of its dense covariance matrix. To

tackle this problem, we examine the geometry of the Gaussian process dataset and propose a

method to solve the covariance matrix linear system using sampling techniques and low-rank

approximation. We then validate the effectiveness of our method through theoretical analysis

and several numerical experiments.

Table of Contents

1 Introduction 1

2 Iterative Methods 3

2.1 Conjugate Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Preconditioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.3 Existing Preconditioners for Conjugate Gradient . . . . . . . . . . . . . . 6

2.3.1 Jacobi Preconditioner . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.3.2 Incomplete Cholesky Preconditioner . . . . . . . . . . . . . . . . . 6

2.3.3 Spatial Data and Factorized Sparse Approximate Inverse . . . . . 7

3 Another View of the Cholesky Factorization 10

3.1 Low-Rank Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.2 Pivoted Cholesky Factorization . . . . . . . . . . . . . . . . . . . . . . . 13

4 Inducing Points Selection 16

4.1 Motivation from Spatial Statistics . . . . . . . . . . . . . . . . . . . . . . 16

4.2 Farthest Point Sampling Method . . . . . . . . . . . . . . . . . . . . . . 18

4.2.1 The Method Overview . . . . . . . . . . . . . . . . . . . . . . . . 18

4.2.2 The First Point of the FPS . . . . . . . . . . . . . . . . . . . . . . 20

4.2.3 Reducing the Repetitive Computation . . . . . . . . . . . . . . . 21

4.2.4 Applying Domain Decomposition . . . . . . . . . . . . . . . . . . 21

5 Theoretical Analysis 24

6 Numerical Experiments 27

6.1 Number of Large Elements for the Cholesky Factor . . . . . . . . . . . . 27

6.2 Low-rank Approximation Comparison . . . . . . . . . . . . . . . . . . . . 30

6.3 Solving Linear Systems and Related Applications . . . . . . . . . . . . . 31

7 Conclusions 36

References 37

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
Department
Degree
Submission
Language
  • English
Research Field
Keyword
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Supplemental Files