Let a gaussian kernel be defined as $K(x_i, x_j) \equiv \exp(-\alpha |x_i-x_j|^2)+\beta \delta_{ij}$, and define the kernel matrix of some set of datapoints $\{x_i\}_{i=1}^n$ as the $n\times n$ matrix $K$ with $K_{ij} = K(x_i, x_j)$.

This is a common construction in various fields, e.g. Gaussian Processes. Is there a fast way of calculating the inverse of the kernel matrix?

Thoughts: if we could break down the matrix $K$ into the form $\beta I + u u^T$ for some column vector $u$, we could use the Sherman–Morrison formula to quickly calculate the inverse, however, we know such a $u$ would be infinite dimensional. Is there another trick one could use?

  • 1
    $\begingroup$ Were you able to make any progress in this problem. I was also additionally interested in the properties of this matrix apart from positive semi-definitiness. $\endgroup$ – dineshdileep Feb 3 '19 at 12:58
  • $\begingroup$ @dineshdileep - No, but thinking about it some more, it's unlikely this has a nice solution, otherwise I'd expect to find it in one of the many texts on GP's. $\endgroup$ – nbubis Feb 4 '19 at 20:20
  • 1
    $\begingroup$ This source covers some approximation methods for the inverse: gaussianprocess.org/gpml/chapters/RW8.pdf. I have also run into the same problem, albeit from a computational standpoint: inverting the Kernel matrix for a large number of datapoints yields memory errors as the computation exceeds the amount of RAM I have on hand. $\endgroup$ – Sentient May 25 '19 at 4:28
  • $\begingroup$ @Sentient - I'll accept that as an answer if you can add a bit more detail about the contents in that link. $\endgroup$ – nbubis May 26 '19 at 4:39

Much works has been done on the scalability of Gaussian Processes. The main idea is to approximate your kernel matrix $K$ with another matrix that admits faster operations. This allows us to have fast matrix vector multiplications when optimizing hyper-parameters and use iterative algorithms such as Conjugate Gradients or GMRES to invert $K$.

The Structured Kernel Interpolation(SKI) paper gives a method for approximating your data with data on a grid, which allows you to use inducing point methods, toeplitz, kronecker methods to get the fast computations. See https://arxiv.org/abs/1503.01057


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.