Fast Direct Methods for Gaussian Processes.

Area of Science:

• Statistics
• Computational Mathematics
• Machine Learning

Background:

• Multivariate normal (Gaussian) distribution is crucial for probability and statistics.
• High-dimensional Gaussian probability calculations require covariance matrix inversion and determinant evaluation, typically O(n^3).
• Covariance matrices in Gaussian processes (C = σ(2)I + K) are often dense, hindering large-scale applications.

Purpose of the Study:

• To develop a computationally efficient algorithm for high-dimensional Gaussian probability calculations.
• To address the O(n^3) complexity bottleneck in covariance matrix operations.
• To enable practical application of Gaussian processes in large-scale modeling.

Main Methods:

• Hierarchical factorization of covariance matrices into block low-rank updates of the identity matrix.
• Development of an O(n log(2) n) algorithm for matrix inversion.
• Extension of the factorization to enable determinant evaluation.

Main Results:

• An efficient O(n log(2) n) algorithm for inverting and evaluating the determinant of specific covariance matrices.
• Demonstrated feasibility of calculating high-dimensional probabilities under broad kernel assumptions.
• Significant reduction in computational cost compared to standard O(n^3) methods.

Conclusions:

• The new algorithm makes complex problems in marginalization and hyperparameter adaptation tractable.
• Enables modeling of previously intractable problems by combining near-optimal scaling with high-performance computing.
• Illustrates practical performance on standard covariance kernels.