%0 Journal Article %1 ambikasaran2014direct %A Ambikasaran, Sivaram %A Foreman-Mackey, Daniel %A Greengard, Leslie %A Hogg, David W. %A O'Neil, Michael %D 2014 %K gaussian-proceses kernels %T Fast Direct Methods for Gaussian Processes %U http://arxiv.org/abs/1403.6015 %X A number of problems in probability and statistics can be addressed using the multivariate normal (Gaussian) distribution. In the one-dimensional case, computing the probability for a given mean and variance simply requires the evaluation of the corresponding Gaussian density. In the $n$-dimensional setting, however, it requires the inversion of an $n n$ covariance matrix, $C$, as well as the evaluation of its determinant, $\det(C)$. In many cases, such as regression using Gaussian processes, the covariance matrix is of the form $C = \sigma^2 I + K$, where $K$ is computed using a specified covariance kernel which depends on the data and additional parameters (hyperparameters). The matrix $C$ is typically dense, causing standard direct methods for inversion and determinant evaluation to require $O(n^3)$ work. This cost is prohibitive for large-scale modeling. Here, we show that for the most commonly used covariance functions, the matrix $C$ can be hierarchically factored into a product of block low-rank updates of the identity matrix, yielding an $O (nłog^2 n) $ algorithm for inversion. More importantly, we show that this factorization enables the evaluation of the determinant $\det(C)$, permitting the direct calculation of probabilities in high dimensions under fairly broad assumptions on the kernel defining $K$. Our fast algorithm brings many problems in marginalization and the adaptation of hyperparameters within practical reach using a single CPU core. The combination of nearly optimal scaling in terms of problem size with high-performance computing resources will permit the modeling of previously intractable problems. We illustrate the performance of the scheme on standard covariance kernels.

@article{ambikasaran2014direct, abstract = {A number of problems in probability and statistics can be addressed using the multivariate normal (Gaussian) distribution. In the one-dimensional case, computing the probability for a given mean and variance simply requires the evaluation of the corresponding Gaussian density. In the $n$-dimensional setting, however, it requires the inversion of an $n \times n$ covariance matrix, $C$, as well as the evaluation of its determinant, $\det(C)$. In many cases, such as regression using Gaussian processes, the covariance matrix is of the form $C = \sigma^2 I + K$, where $K$ is computed using a specified covariance kernel which depends on the data and additional parameters (hyperparameters). The matrix $C$ is typically dense, causing standard direct methods for inversion and determinant evaluation to require $\mathcal O(n^3)$ work. This cost is prohibitive for large-scale modeling. Here, we show that for the most commonly used covariance functions, the matrix $C$ can be hierarchically factored into a product of block low-rank updates of the identity matrix, yielding an $\mathcal O (n\log^2 n) $ algorithm for inversion. More importantly, we show that this factorization enables the evaluation of the determinant $\det(C)$, permitting the direct calculation of probabilities in high dimensions under fairly broad assumptions on the kernel defining $K$. Our fast algorithm brings many problems in marginalization and the adaptation of hyperparameters within practical reach using a single CPU core. The combination of nearly optimal scaling in terms of problem size with high-performance computing resources will permit the modeling of previously intractable problems. We illustrate the performance of the scheme on standard covariance kernels.}, added-at = {2019-08-22T20:32:29.000+0200}, author = {Ambikasaran, Sivaram and Foreman-Mackey, Daniel and Greengard, Leslie and Hogg, David W. and O'Neil, Michael}, biburl = {https://www.bibsonomy.org/bibtex/28bb99b4e79b40a692c416b8ea6177744/kirk86}, description = {[1403.6015] Fast Direct Methods for Gaussian Processes}, interhash = {636b7e5672c18316eb790048f406ca48}, intrahash = {8bb99b4e79b40a692c416b8ea6177744}, keywords = {gaussian-proceses kernels}, note = {cite arxiv:1403.6015}, timestamp = {2019-08-22T20:32:29.000+0200}, title = {Fast Direct Methods for Gaussian Processes}, url = {http://arxiv.org/abs/1403.6015}, year = 2014 }