# Prove that the variance of a Gaussian Process is minimum on its train data points

I want to prove that the variance of a Gaussian Process (GP) is the lowest on any one of its $$p$$ training data points.

The prior distribution for a zero-mean GP prior, with kernel function $$k(x, x')$$ is, $$P\left( \begin{bmatrix} y_{*} \\ Y \end{bmatrix} \right) = \mathcal{N} \left(0, \begin{bmatrix} k(x_{*}, x_{*}) & K(x_{*}, X)\\ K(x_{*}, X)^{T} & K(X, X) \end{bmatrix} \right). \,\, (1)$$ Where,

1. $$x_{*}$$ is a new potentially unseen test data point.
2. $$X$$ is the prior seen training data set for which corresponding labels/observations $$Y$$ are available. To be precise X is a matrix with the $$i^{th}$$ row given by data-point $$x_i$$.
3. $$K(x_{*}, X)$$ is a $$p \times 1$$ row-vector with $$i^{th}$$ entry given by $$K(x_{*}, x_i)$$.
4. $$K(X, X)$$ is a $$p \times p$$ matrix with the $$(i, j)^{th}$$ entry being given by $$k(x_i, x_j)$$.
5. I am not considering any observation noise in the problem which means that labels and observations are identical and given by $$y$$.

For the above prior distribution, the covariance of the posterior distribution over the predicted label $$y_{*}$$ will be, $$\sigma_{y_{*}} = k(x_{*}, x_{*}) - K(x_{*}, X)K(X, X)^{-1}K(x_{*}, X)^{T}. \,\,(2)$$ Where I have used the formula for the covariance of a conditional multivariate normal (MVN) random variable as is done in [1].

Among other requirements, kernel functions $$k$$ satisfy, $$k(x, x) = 1$$ so $$\sigma_{y_{*}}$$ being minimum for seen points present in $$X$$ is equivalent to, $$\arg \max_{x_{*}} K(x_{*}, X)K(X, X)^{-1}K(x_{*}, X)^{T} = x_i \, \, \forall \, i \in [p]. \,\,(3)$$

To try and prove the condition $$(3)$$, I have tried the following approaches,

1. The result is clearly true for $$p=1$$ since then the term in $$(3)$$ becomes $$k(x_{*}, x_1)k(x_{1}, x_{1})^{-1}k(x_{*}, x_1)$$ which will be maximum when $$x_{*} = x_{1}$$. So I tried writing out the product in $$(3)$$ for the case $$p = 2$$ to see if I could find a reason for it being maximized on points in $$X$$. For $$p=2$$ the expression in $$(3)$$ was, $$k(x_{*}, x_1)^{2} + k(x_{*}, x_2)^{2} - 2 k(x_1, x_2) k(x_{*}, x_1) k(x_{*}, x_2).$$ For this $$p = 2$$ case $$X = [x_1^{T} \, x_2^{T}]^{T}$$ and I don't see why we'll have maximums at $$x_{*} = x_1$$ and $$x_{*} = x_2$$.
2. Next I tried putting in the RBF/Squared-Exponential kernel $$k(x, x') = \exp{\left(-\frac{1}{2 l_{d}^2} (x - x') \right)}$$ into the expression for $$p=2$$ I got above and took the derivative of the expression with respect to $$x_{*}$$ and set this derivative to 0. While plugging in $$x_1$$ and $$x_2$$ does make the derivative evaluate to $$0$$ it is not clear if those two will be the only solutions to the equation
3. Since I could see the result holding for $$p=1$$ I thought of trying an inductive approach where I assume that $$(3)$$ holds for some $$p=m$$ and I attempt to extend it to $$p=m+1$$ by expanding $$k(x_{*}, X_{p})$$ to $$[k(x_{*}, X_{p}) \,\, k(x_{*}, x_{p + 1})]$$ and analogously expanding $$K_{XX}$$; however I don't think optimization problems (or at least this problem) can be fit into an inductive framework.
4. An argument for the result is that $$\sigma_{y_{*}}$$ can only be a valid variance if the expression in $$(2)$$ $$\geq 0$$. This in turn requires that, $$K(x_{*}, X)K(X, X)^{-1}K(x_{*}, X)^{T} \leq k(x_{*}, x_{*}) = 1. \,\, (4)$$ Now it easy to show that $$\sigma_{y_{*}} = 0$$ when $$x_{*}$$ is a test-point from $$X$$ so by (4) we get the required result of the variance being minimum and equal to $$0$$ on test-points. However I am discounting this argument as circular.
• There is nothing circular about your argument 4: you've shown that a given function is nonnegative, and then you've found a point at which it takes value 0. This point is necessarily a global minimizer; it's a sound argument. Now, it does not imply that there won't be some non-training point that also has zero variance. Actually, this will be the case for certain kernels, notably tensor sum kernels. See e.g. arxiv.org/pdf/1112.4394.pdf. Commented Feb 20 at 23:45

For noise free case, when $$x_* = x_i$$ for some i, then $$k(x_*, X)$$ is the $$i$$th column of $$K(X,X)$$. Thus, you obtain

$$K(X,X)^{-1} k(x_i,X)^T = \mathbf{e}_i$$ where $$\mathbf{e}_i$$ denotes a standard basis of $$\mathbb{R}^N$$

Thus, $$\sigma_{y_*} = k(x_i , x_i) - k(x_i, X) \mathbf{e}_i = k(x_i, x_i) - k(x_i, x_i) = 0$$ and this is global minimum.