# Positive definiteness of Grammian with respect to Gaussian process' covariance function

A Gaussian process indexed by $T \subseteq \mathbb{R}^d$ is a collection of random variables $\{ X_t : t \in T\}$, for which each finite subset is distributed as a multivariate Gaussian.

Let $G$ be a sample path of a Gaussian process having mean zero and covariance function $K$, where $K: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}, K(t,s)=\operatorname{Cov}(X_s,X_t)$. Let $(x_1,...,x_n)$ be a finite sequence of points where $x_i \in \mathbb{R}^d$ and let $M$ denote the Gram matrix $$M(x_1,...,x_n) = \begin{pmatrix} K(x_1,x_1) & \cdots & K(x_1,x_n) \\ \vdots & \ddots & \vdots \\ K(x_n,x_1) & \cdots & K(x_n,x_n) \end{pmatrix} .$$

Is matrix $M$ positive definite (and therefore invertible) for any choice of covariance function $K$? If so, why?

UPDATE:

What if the points $(x_1,...,x_n)$ are distinct? Does that guarantee that Grammian M is positive definite?

## 1 Answer

For us to have a Gaussian Process, our covariance function $k(x_i,x_j)$ itself has to be positive semi-definite which is defined as so:

A symmetric function $k:\mathcal{X}\times \mathcal{X} \rightarrow \mathbb{R}$ is a positive definite kernel on $\mathcal{X}$ if $$\sum_i^n \sum_j^n k(x_i,x_j)c_ic_j \geq 0$$ holds for any $n \in \mathbb{N}$, $x_1, ..., x_n \in \mathcal{X}$ and $c_1, ..., c_n \in \mathbb{R}$.

Thus, since the definition of the Gram matrix is $M_{ij} = k(x_i,x_j)$ as you write, and the definition of a positive semi-definite matrix is $x^\top Mx \geq f, \forall x \in \mathcal{X}$, we only have to rewrite this quadratic form $$x^\top Mx = \sum_i^n \sum_j^n M_{ij}x_i x_j = \sum_i^n \sum_j^n k(x_i,x_j)x_i x_j$$ to see that $M$ is a positive semi-definite matrix (since $x_1, ..., x_n \in \mathbb{R}$).

• Thanks a lot for your insightful answer! Just to make sure, since positive semi-definiteness is not the same as positive definiteness the answer to my question, namely that M is a positive definite matrix for any choice of K, is no? Commented Jul 19, 2018 at 14:37
• Yes! A positive definite kernel function only implies a positive semi-definite Gram matrix. Having said that, your eigenvalues will often all be positive (i.e. positive definite matrix), depending on your data. But yes, you could have 0's as well. Furthermore, note that you can run into numerical trouble trying to invert your Gram matrix, the solution to which is to add a small value $\delta$ to the daigonal. Commented Jul 19, 2018 at 15:17
• One more question. What if the points $(x_1,...,x_n)$ are distinct? Does that guarantee that Grammian M is positive definite? Commented Jul 19, 2018 at 17:49
• Interesting question, it depends on your kernel. It's surely not the case for the bias and some polynomial kernels. It might be the case for stationary kernels, but I am afraid this is the limit of my knowledge. For sure, with all kinds of kernels when you have replicates or very similar values you can run into numerical problems. Commented Jul 20, 2018 at 10:28
• "A positive definite kernel function only implies a positive semi-definite Gram matrix" I take it you do not distinguish between positive definite and positive semi-definite kernels and apply the definition with non-strict inequality to both? I suppose @MetodJazbec differentiated between the two types of kernels in his/her comments; just like Wikipedia does: en.wikipedia.org/wiki/… Commented Jul 1, 2021 at 17:53