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?

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? – Metod Jazbec Jul 19 '18 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. – Daniel Svendsen Jul 19 '18 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? – Metod Jazbec Jul 19 '18 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. – Daniel Svendsen Jul 20 '18 at 10:28