= Solution
Use only the first $n-1$ observations to define
$$
\begin{aligned}
A&=(k(x_i,x_j))_{i,j<n}+\sigma^2I_{n-1},&
b&=(k(x_i,x_n))_{i<n},\\
a&=(k(x_i,x_*))_{i<n},&
c&=k(x_n,x_n)+\sigma^2,\\
d&=k(x_n,x_*),&k_{**}&=k(x_*,x_*).
\end{aligned}
$$
Thus the full noisy <covariance matrix> is $C_n=\begin{pmatrix}A&b\\b^T&c\end{pmatrix}$ and the full cross-covariance <vector> is $(a^T,d)^T$. Set
$$
s=c-b^TA^{-1}b,\qquad M=s^{-1}.
$$
The scalar $s$ is the <Schur complement> of $A$. Substituting the block inverse into the <Gaussian process regression posterior> <variance> gives
$$
\begin{aligned}
v_n(x_*)&=k_{**}-\begin{pmatrix}a^T&d\end{pmatrix}C_n^{-1}\begin{pmatrix}a\\d\end{pmatrix}\\
&=k_{**}-a^TA^{-1}a-M\left[(a^TA^{-1}b)^2-2d\,a^TA^{-1}b+d^2\right]\\
&=v_{n-1}(x_*)-M(d-b^TA^{-1}a)^2.
\end{aligned}
$$
Consequently,
$$
\boxed{c_1=\frac1{k(x_n,x_n)+\sigma^2-b^TA^{-1}b},\qquad c_2=b^TA^{-1}a},
$$
and
$$
\boxed{\operatorname{Var}_{n-1}(f_*)-\operatorname{Var}_n(f_*)=c_1\bigl(k(x_n,x_*)-c_2\bigr)^2}.
$$
For interpretation, after the first $n-1$ observations the remaining <covariance> between $f_*$ and $f(x_n)$ is $r=d-b^TA^{-1}a$, while the <conditional variance> of the new noisy observation is $s$. Thus the reduction is the squared remaining <covariance> divided by the remaining observation <variance>.
Back to article page
