Efficient Preconditioner for Covariance Matrices Using Geometric Information Public

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	Emory College
Department	Mathematics
Degree	B.S.
Submission	Honors Thesis
Language	English
Research Field	Applied Mathematics
Mot-clé	Preconditioning Gaussian Process Low-rank Approximation Iterative Methods
Committee Chair / Thesis Advisor	Yuanzhe Xi, Emory University
Committee Members	James G. Nagy, Emory University Joyce C. Ho, Emory University

Dernière modification

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Efficient Preconditioner for Covariance Matrices Using Geometric Information ()	2022-04-12 20:26:01 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions