# RKHS norm and posterior of Gaussian process

In Srinivas et al (2010) [appendix B], the authors claim the following "easy to see" property relating the norm of a function in a RKHS induced by a kernel $k(\cdot,\cdot)$, and its norm in the RKHS induced by the posterior covariance of a Gaussian process with the same kernel $k(\cdot,\cdot)$. I'm unable to see why this claim is correct:

Definitions: Let $k:\mathcal{X} \times \mathcal{X} \to \mathbb{R}^+$ be a kernel function and $\mathcal{H}_k$ the associated RKHS. Let $x_1, \dots, x_T$ be a finite sequence of points in $\mathcal{X}$. The posterior covariance function of a Gaussian process of kernel $k$ perturbed by independent $\mathcal{N}(0,\sigma^2)$ noise is: $$k_T(x,y) := k(x,y) - \mathrm{k}_T^\top(x)\Big(\mathrm{K}_T+\sigma^2\mathrm{I}\Big)^{-1}\mathrm{k}_T(y)\,,$$ where the $(T\times 1)$-vector $\mathrm{k}_T$ is defined by $\big[\mathrm{k}_T(x)\big]_t := k(x_t,x)$ and the $(T\times T)$-matrix $\mathrm{K}_T$ by $\big[\mathrm{K}_T\big]_{t,t'} := k(x_t,x_{t'})$.
Let $\mathcal{H}_{k_T}$ be the associated RKHS.

Question: Show that $\mathcal{H}_k = \mathcal{H}_{k_T}$ and for all $f\in \mathcal{H}_k$: $$\|f\|_{k_T}^2 = \|f\|_k^2 + \sigma^{-2} \sum_{t=1}^T f(x_t)^2\,.$$

• We can remark that if we drop the term $\sigma^2 \mathrm{I}$, the transformation can be viewed as a projection where we remove the space generated by the $\{x_t\}_{t\leq T}$. Then, the new norm can be related to the other using Pythagorean theorem. Sep 29, 2014 at 11:27
• Were you able to figure this out? Feb 7, 2018 at 20:05

I am reading this paper and met with this problem today. I am not familiar with reproducing kernel hilbert space, but after reading a lot, in my opinion it seems that here there are two groups basis: $$k(·,x_t)_{t=1}^{T}\;\text{ and }\;k_T(·,x_t)_{t=1}^{T}$$ for the same hilbert functional space which consists of the linear combination of the basis. So what should we do is to find out the specific relation between the coefficients of two different basis for the same element. I just figured it out moments ago, and I happened to see your question, though eight years ago. Really time test, right? I am tired so I just put my drafts here to answer it.