Fast Matrix Square Roots with Applications to Gaussian Processes and Bayesian Optimization Article Swipe

MAKE IMPACT

Geoff Pleiss , Martin Jankowiak , David Eriksson , Anil Damle , Jacob R. Gardner · YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2006.11267

Matrix square roots and their inverses arise frequently in machine learning, e.g., when sampling from high-dimensional Gaussians $\mathcal{N}(\mathbf 0, \mathbf K)$ or whitening a vector $\mathbf b$ against covariance matrix $\mathbf K$. While existing methods typically require $O(N^3)$ computation, we introduce a highly-efficient quadratic-time algorithm for computing $\mathbf K^{1/2} \mathbf b$, $\mathbf K^{-1/2} \mathbf b$, and their derivatives through matrix-vector multiplication (MVMs). Our method combines Krylov subspace methods with a rational approximation and typically achieves $4$ decimal places of accuracy with fewer than $100$ MVMs. Moreover, the backward pass requires little additional computation. We demonstrate our method's applicability on matrices as large as $50,\!000 \times 50,\!000$ - well beyond traditional methods - with little approximation error. Applying this increased scalability to variational Gaussian processes, Bayesian optimization, and Gibbs sampling results in more powerful models with higher accuracy.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2006.11267

PDF

https://arxiv.org/pdf/2006.11267

OA Status

green

Cited By

11

References

79

Related Works

10

OpenAlex ID

https://openalex.org/W3036520005

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W3036520005

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2006.11267

Digital Object Identifier

Title

Fast Matrix Square Roots with Applications to Gaussian Processes and Bayesian Optimization

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2020

Year of publication

Publication date

2020-06-19

Full publication date if available

Authors

Geoff Pleiss, Martin Jankowiak, David Eriksson, Anil Damle, Jacob R. Gardner

List of authors in order

Landing page

https://arxiv.org/abs/2006.11267

Publisher landing page

PDF URL

https://arxiv.org/pdf/2006.11267

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2006.11267

Direct OA link when available

Concepts

Krylov subspace, Matrix (chemical analysis), Computation, Mathematics, Gaussian, Algorithm, Quadratic equation, Gibbs sampling, Sampling (signal processing), Applied mathematics, Covariance matrix, Square matrix, Multiplication (music), Bayesian probability, Eigenvalues and eigenvectors, Combinatorics, Computer science, Physics, Symmetric matrix, Quantum mechanics, Statistics, Iterative method, Materials science, Geometry, Filter (signal processing), Composite material, Computer vision

Top concepts (fields/topics) attached by OpenAlex

Cited by

11

Total citation count in OpenAlex

Citations by year (recent)

2024: 2, 2023: 2, 2022: 1, 2021: 5, 2020: 1

Per-year citation counts (last 5 years)

References (count)

79

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload