3
$\begingroup$

I'm currently concerned with the topic of Gaussian Processes. To compute the covariance matrix of the conditional distribution, we have to invert $(K_{XX})^{-1}$, where $K_{XX}$ is a matrix of a kernel function $k(x_i, x_j)$ evaluated on all pairwise training samples.

For a matrix to always have an inverse, it has to be positive definite (pd.).

However, when we check for the validity of kernels, it is often based on Mercer's Theorem and this seems to only ensure positive semi-definiteness (psd.). https://las.inf.ethz.ch/courses/introml-s20/tutorials/tutorial5-kernels2.pdf (ETH Zürich, Slide 13). https://people.eecs.berkeley.edu/~jordan/courses/281B-spring04/lectures/lec3.pdf (Berkley, Page 4).

But positive semi-definite kernels produce positive semi-definite matrices.

Could someone explain where my misconception is?
Are there valid kernels for which we get a psd matrix which may not be invertible and the Gaussian Process fails?

Edit: I know the kernels we classically use are pd as listed here: https://en.wikipedia.org/wiki/Positive-definite_kernel.
This seems to be related to the unanswered post from Is a valid kernel function have to be positive definite?

$\endgroup$
1
  • 1
    $\begingroup$ there is no need for the kernel matrix to be positive definite: positive semidefiniteness is enough. It's true: the way practioners of GP regression tend to use numerical linear algebra requires the kernel matrix to be of full numerical rank. (this is actually not necessary from a theoretical perspective, and using pseudo-inverses gives perfectly fine results in many cases, but let's set that aside for the moment). However, from a practical perspective, even if a kernel is theoretically positive definite, in practice the kernel matrix will still be numerically singular. $\endgroup$ May 12, 2023 at 17:51

1 Answer 1

3
$\begingroup$

You have not told us what you consider a valid kernel, so I can't comment on that. But I can give you a reason why one likes to consider positive semi-definite kernels and not just positive definite ones. Just consider the following kernel:

$$ K:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}\quad,\quad K(x,y)=xy.$$

This may be just the canonical inner product on $\mathbb{R}$ but defines a decent real reproducing kernel Hilbert-space (RKHS) and $K$ is its reproducing kernel. The kernel even has a name: linear kernel. But notice that the kernel matrix for the points $x=1$ and $y=2$ is $$ \begin{pmatrix} 1 & 2\\2 & 4\end{pmatrix}$$ hence semi-definite.

This is no accident. Consider the canonical feature map of this RKHS. This is the map which associates with a point $x\in\mathbb{R}$ the function (= vector in the RKHS) $k_x$ with the property that $k_x(z)=K(x,z)=xz.$ It is not difficult to see that for any two points $x,y$ the respective functions $k_x$ and $k_y$ are scalar multiples of each other. Since the canonical features span the RKHS, you can conclude that the feature space is one-dimensional and in a one-dimensional space each Gram-Matrix (=Kernel matrix) has at most rank one.

This generalizes to feature spaces of arbitrary but finite dimension, where the kernel is defined on an infinite set. If your feature space is $n$-dimensional you pick $n+1$ points and the according feature vectors will be linearly dependent and their Gram/Kernel Matrix semi-definite.

To conclude, insisting on positive definite Kernels, would exclude finite dimensional RKHS, which does not make a lot of sense.

And of course if you want all Kernel matrices invertible, on infinite domains of definition, you need a Kernel with infinite dimensional feature space.

$\endgroup$
1
  • 1
    $\begingroup$ "And of course if you want all Kernel matrices invertible, on infinite domains of definition, you need a Kernel with infinite dimensional feature space." note that this is only sufficient for the "true" rank of the kernel matrix; it will be insufficient for the numerical rank of a kernel matrix stored on a computer. $\endgroup$ May 12, 2023 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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