Effect of measurement variance on predictive variance in Gaussian Processes When performing Gaussian process regression, the variance at a prediction point is given by 
$\operatorname{var}[f_*] = k(x_*,x_*) - k_*^T(K+\sigma_n^2I)^{-1}k_*$ (Equation 2.26 from GPML)
Basic statistical intuition tells me that this value should always be positive, but I can't figure out how to prove that. 
 A: Covariance matrices are the variance times correlation (a value that ranges between 0 and 1). I won't prove the general case now as I just woke up, but let's do a 2D case, then $k_*^T(K + \sigma_n^2I)^{-1})k_* = \sigma_*\rho\sigma(\sigma^2 + \sigma_n^2)^{-1}\sigma\rho\sigma_* \lt \sigma_*^2\rho^2 \lt \sigma_*^2 = k(x_*,x_*)$. Hence $\operatorname{var}[f_*] \geq 0.$
A: One might argue that you do not need to use your intuition or proof anything to conclude that the expression is positive since it is the variance of a random normal variable. If you believed the prior proof no further analysis were necessary.
But it is possible to rewrite the variance expression in a way that the reason for the non-negativeness becomes clear. For simplicity assume the process is zero mean. We work in the $(n+1)$-dimensional vector space spanned by the random variables at the points of observation $x_1,\ldots, x_n$ and the prediction point $x_*$. The covariance defines a scalar product on this space where $K_{i,j}=<x_i, x_j>$, $(k_*)_j=<x_*, x_j>$ and $k_{**}=<x_*,x_*>$.
Now decompose your prediction variable $x_*$ into two parts, a part $z$ orthogonal to and a part $x_0$ within the subspace spanned by $x_1,\ldots, x_n$, i.e. write $x_*=z+x_0$ with $x_0 = \sum_j \beta_j x_j = X\beta$ and $<z,x_j>=0$ for all $j$. Note for later that $<x_*, x_i>=<X\beta,x_i>$, which means $K\beta = k_*$ or $\beta = K^{-1}k_*$.
Now $$<z,z>=<x_*-x_0,x_*-x_0> = <x_*,x_*> - <x_0,x_0>$$ and the claim follows by noticing that $<x_*,x_*>=k_{**}$ and $$<x_0,x_0>=<X\beta,X\beta>=\beta^T K \beta$$ where $$ \beta^T K\beta = (K^{-1}k_*)^T K K^{-1}k_* = k_*^T K^{-1} k_*.$$Since $<,>$ is a scalar product, $<z,z>$ is non-negative and your question answered. But this derivation also shows how the prediction can be split into a part $x_0$ explained by the observations and a part $z$ uncorrelated to those and this latter part is what remains after conditioning on the observations.
