RKHS norm and posterior of Gaussian process

Question

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\,.$$

Answer 1

I've been stuck with that statement as well in the past, especially regarding the RKHS norm equation. There are different ways to prove it, but one that involves just simple linear algebra and feature maps is the following.

Let $\phi: \mathcal{X} \to \mathcal{H}_k$ denote the canonical feature map, i.e., $\phi(x) = k(\cdot, x)$, for $x \in \mathcal{X}$. Now define an operator $\mathrm{W}_t:\mathcal{H}_k\to\mathcal{H}_k$ as: \begin{equation} \mathrm{W}_t := \sigma^{-2}\Phi_t\Phi_t^\mathtt{T} + I, \end{equation} where $\Phi_t := [\phi(x_1), \dots, \phi(x_t)]: \mathbb{R}^t\to\mathcal{H}_k$ and $A^\mathtt{T}$ denotes the transpose or adjoint of operator $A$. Note that in general we can treat $\mathrm{W}_t$ as a (infinite-dimensional) matrix. Since $\mathrm{W}_t$ is positive definite, it has an inverse. Applying Woodbury's identity yields: \begin{equation} \mathrm{W}_t^{-1} = (\sigma^{-2}\Phi_t\Phi_t^\mathtt{T} + I)^{-1} = I - \Phi_t(\sigma^2 I + \Phi_t^\mathtt{T}\Phi_t)^{-1}\Phi_t^\mathtt{T} = I - \Phi_t(\mathrm{K}_t + \sigma^2 I)^{-1}\Phi_t^\mathtt{T} \,. \end{equation} We then see that the GP posterior kernel $k_t$ can be obtained as: \begin{equation} \begin{split} \langle \phi(x), \mathrm{W}_t^{-1} \phi(x') \rangle_k &= \langle \phi(x), \phi(x') \rangle_k - \phi(x)^\mathtt{T} \Phi_t(\mathrm{K}_t + \sigma^2 I)^{-1}\Phi_t^\mathtt{T}\phi(x')\\ &= k(x,x') - \mathrm{k}_t(x)^\mathtt{T} \Phi_t(\mathrm{K}_t + \sigma^2 I)^{-1}\mathrm{k}_t(x')\\ &= k_t(x,x')\,. \end{split} \end{equation}

Now observe that $\mathrm{W}_t^{-1/2} \phi : \mathcal{X} \to \mathcal{H}_k$ defines a (non-canonical) feature map for $k_t$, using $\mathcal{H}_k$ as the feature space, since $\langle \mathrm{W}_t^{-1/2} \phi(x), \mathrm{W}_t^{-1/2} \phi(x') \rangle_k = \langle \phi(x), \mathrm{W}_t^{-1} \phi(x') \rangle_k = k_t(x,x')$. By the reproducing property, for any $f \in \mathcal{H}_{k}$, we have that: \begin{equation} \begin{split} \forall x \in \mathcal{X}, \quad f(x) = \langle f, \phi(x) \rangle_k &= \langle f, \mathrm{W}_t^{1/2} \mathrm{W}_t^{-1/2} \phi(x) \rangle_k\\ &= \langle \mathrm{W}_t^{1/2} f, \mathrm{W}_t^{-1/2} \phi(x) \rangle_k\\ &= \langle f, k_t(\cdot, x) \rangle_{k_t} \end{split} \end{equation} Therefore, $\mathrm{W}_t^{1/2} f$ is the representation of $f \in \mathcal{H}_{k_t}$ in the feature space. The norm of $f$ is then given by: \begin{equation} \begin{split} \lVert f \rVert_{k_t}^2 &= \langle \mathrm{W}_t^{1/2} f, \mathrm{W}_t^{1/2} f \rangle_k\\ &= \langle f, \mathrm{W}_t f \rangle_k\\ &= f^\mathtt{T} (\sigma^{-2}\Phi_t\Phi_t^\mathtt{T} + I) f\\ &= \lVert f \rVert_k^2 + \sigma^{-2} f^\mathtt{T} \Phi_t\Phi_t^\mathtt{T} f\\ &= \lVert f \rVert_k^2 + \sigma^{-2} \sum_{i=1}^t f(x_i)^2\,, \end{split} \end{equation} since $\Phi_t^\mathtt{T} f = [f(x_1), \dots, f(x_t)]^\mathtt{T} \in \mathbb{R}^t$.

To prove that $\mathcal{H}_k = \mathcal{H}_{k_t}$, I'm not sure what is the easiest way, but I think one could show that (1) any $f \in \mathcal{H}_k$ has a bounded norm in $\mathcal{H}_{k_t}$, so that $\mathcal{H}_k \subset \mathcal{H}_{k_t}$, and (2) the difference $k - k_t$ defines a positive-semidefinite kernel, which satisfies the main condition for $\mathcal{H}_{k_t} \subset \mathcal{H}_k$ (see, for example, Berlinet & Thomas-Agnan, 2012, sec. 4.5, Thr. 12).

References:

• Berlinet, A., & Thomas-Agnan, C. (2004). Reproducing Kernel Hilbert Spaces in Probability and Statistics. In Reproducing Kernel Hilbert Spaces in Probability and Statistics. Springer. https://doi.org/10.1007/978-1-4419-9096-9

Answer 2

First draft image Second draft image
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.