# Covariance matrix computed based on a covariance function

I am reading Chapter 4 of Gaussian Processes for Machine Learning. It says that a matrix $K$ whose entries are computed as $k_{ij} = k(x_i, x_j)$ where $k$ is a covariance function is a positive semidefinite matrix.

Consider the exponential kernel

$$k(x_i, x_j) = k(|x_i - x_j|) = k(d_{ij}) = \exp\left(-\frac{d_{ij}}{10}\right)$$

and the matrix

$$D = (d_{ij}) = \left(\begin{array}{cccc} 0 & 1 & 3 & 1\\ 1 & 0 & 2 & 3\\ 3 & 2 & 0 & 1\\ 1 & 3 & 1 & 0\\ \end{array}\right).$$

I compute my potential covariance matrix $K$ by evaluating the kernel at the corresponding entries of $D$, that is,

$$K = (k_{ij}) = (k(d_{ij})).$$

The resulting matrix, however, seems to have one negative eigenvalue as shown in the following snippet of MATLAB code:

D = [ 0, 1, 3, 1;
1, 0, 2, 3;
3, 2, 0, 1;
1, 3, 1, 0 ];

eig(exp(-D/10))

ans =

-0.0314
0.2156
0.3078
3.5080


I assume that I misunderstood the material given in that chapter, and I would be grateful if somebody could point out my mistake. Thank you!

Best wishes, Ivan

• Is $D$ supposed to be a matrix of distances? Because here, $d_{24}=3\gt1+1=d_{21}+d_{14}$, hence it is not. – Did Sep 21 '14 at 12:28
• The intuition behind $D$ is, yes, like a distance, but it was computed artificially without trying to satisfy any conditions of a metric. There are probably some additional requirements, which I am not aware of, for being able to do what I am trying to do here. Could you please explain? – Ivan Sep 21 '14 at 12:39
• If you are referring to (4.18) (for $\gamma=1$), indeed this yields a covariance function when $|r|$ in the formula is a distance since $r$ stands for $x_i-x_j$, but not for every set of "distances" $|r|$. This is why your matrix $D$ fails, I believe. – Did Sep 21 '14 at 12:46
• Yes, I see now. I very conveniently jumped over $|x_i - x_j|$ and have been disregarding it thereafter. Thanks a lot! – Ivan Sep 21 '14 at 12:49

Is D supposed to be a matrix of distances? Because here, $d_{24}=3>1+1=d_{21}+d_{14}$, hence it is not. If you are referring to (4.18) (for $\gamma=1$), indeed this yields a covariance function when $|r|$ in the formula is a distance since $r$ stands for $x_i−x_j$, but not for every set of “distances” $|r|$. This is why your matrix $D$ fails, I believe.