# Inverse of Gaussian Kernel Matrix

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?

• 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. – dineshdileep Feb 3 '19 at 12:58
• @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. – nbubis Feb 4 '19 at 20:20
• 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. – Sentient May 25 '19 at 4:28
• @Sentient - I'll accept that as an answer if you can add a bit more detail about the contents in that link. – 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$$.