# 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.

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