How to calculate RKHS norm of a function under given kernel transformation

Question

This was a question asked before in mathoverflow but not yet got answered. I have the same problem when reading Srinivas et al (2010) [appendix B]'s paper.

Here are my problems:

Definitions: Let $k:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}^+$ be a kernel function and $H_k$ is the associated RKHS. Let $x_1,…,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,x^\prime)=k(x,x^\prime)-k_T(x)^T(K_T+\sigma^2I)k_T(x^\prime)$$ where $k_T(x)=[ k(x_1,x),...,k(x_T,x)]$, and $K_T(i,j)=k(x_i,x_j)$.

I am quite new to RKHS so I can't understand why the author immediately gets following two observations.

1: $\forall f\in\mathcal{H}_K$, we have $$||f||_{k_T}^2=||f||_{k}^2+\sigma^{-2}\sum_{t=1}^Tf(x_t)^2$$

How can we get this result so fast? And this is done by some well-known lemmas or standard procedures?

2: Result 1 will implies that $$H_{k_{T}}=H_{k}$$

Is it because of that if a function has bounded norm in $H_{k_{T}}$ then $H_{k}$ and vice versa?

Answer 1

As shown at the page 26 in http://www2.stat.duke.edu/~sayan/Sta613/2017/lec/nonlin.pdf.

$$ \Vert f \Vert_k^2 := \sum_i \frac{<f,\phi_i>_{L^2}^2}{\lambda_i} $$

where $ \{(\lambda_i, \phi_i(\cdot))\}_{i=1,\cdots} $, ($\lambda_i > 0$), is the eigensystem of the integral operator with the kernel $T_k$

$$ [T_k(f)](\cdot) = \int k(\cdot,y)f(y)dy. $$

Since $\{\phi_i(\cdot)\}_{i=1,\cdots}$ is an orthonormal basis of $L^2$, an eigenfunction of $T_{k_T}$ can be represented as a linear combination of it $$ \psi_n(\cdot) = \sum_i p_i^{(n)} \phi_i(\cdot) $$ with the corresponding eigenvalue $\gamma_n > 0$.

Then $$ [T_{k_T} \psi_n](\cdot) = \gamma_n \psi_n (\cdot) $$ we have $$ [T_{k_T} \psi_n](\cdot) = \int [k(\cdot, y) - k(\cdot, D)(k(D,D)+\sigma^2 I)^{-1}k(D, y)]\psi_n(y) dy $$ where $k(\cdot, D) = k_T(\cdot)$ in the above question.

By substituting the linear combination above into the integral transform $$ \int [k(\cdot, y) - k(\cdot, D)(k(D,D)+\sigma^2 I)^{-1}k(D, y)]\psi_n(y) dy \\ =\sum_i \lambda_n p_i^{(n)} \phi_i(\cdot) - k(\cdot, D)(k(D,D)+\sigma^2 I)^{-1} \sum_i \lambda_n p_i^{(n)} \phi_i(D) $$ where I assume the interchangeability between integral and series, which needs to be checked for rigor but it usually behaves well in RKHS's sufficient regularities.

Taking $L^2$ inner product with $\phi_j(\cdot)$ $$ \lambda_n p_j^{(n)} - \lambda_n \phi_j(D)^T (k(D,D)+\sigma^2 I)^{-1} \sum_i \lambda_n p_i^{(n)} \phi_i(D) $$ again, the interchangeability is assumed here.

From now on, I use infinite dimensional matrix&vector notation which essentially means linear operators&functions on a countable set. Let $$ \Lambda = diag(\lambda_1, \lambda_2, \cdots, ) \\ \mathbf{p}^{(n)} = [p_1^{(n)}, p_2^{(n)}, \cdots, ]^T \in \mathbf{R}^{\aleph_0} \\ \mathbf{\Phi} = [\phi_1(D), \phi_2(D), \cdots, ]^T \in \mathbf{R}^{\aleph_0 \times \vert D \vert} $$ then the above equation can be grouped as $$ \Lambda \mathbf{p}^{(n)} - \Lambda \mathbf{\Phi} (k(D,D)+\sigma^2 I)^{-1} \mathbf{\Phi}^T \Lambda \mathbf{p}^{(n)} = \gamma_n \mathbf{p}^{(n)}. $$

Using Woodbury identity (in Wiki, it is mentioned that this identity holds in a general ring), we have $$ (\Lambda^{-1} + \sigma^{-2} \mathbf{\Phi} \mathbf{\Phi}^T)^{-1} \mathbf{p}^{(n)} = \gamma_n \mathbf{p}^{(n)}. $$

By letting $$ \Gamma = diag(\gamma_1, \gamma_2, \cdots, ) \\ \mathbf{P} = [\mathbf{p}^{(1)}, \mathbf{p}^{(2)}, \cdots, ] \\ \mathbf{c} = [<f,\phi_1>_{L^2}, <f,\phi_2>_{L^2}, \cdots, ]^T $$ then $$ \Lambda^{-1} + \sigma^{-2} \mathbf{\Phi} \mathbf{\Phi}^T = \mathbf{P} \Gamma^{-1} \mathbf{P}^T $$ and $$ \Vert f \Vert_{k_T}^2 = \mathbf{c}^T \mathbf{P} \Gamma^{-1} \mathbf{P}^T \mathbf{c} = \mathbf{c}^T \Lambda^{-1} \mathbf{c} + \sigma^{-2} \mathbf{c}^T \mathbf{\Phi} \mathbf{\Phi}^T \mathbf{c} = \Vert f \Vert_k^2 + \sigma^{-2} \sum_{x \in D} f(x)^2. $$

The last equality follows from the fact that $ \{ \phi_i \}_i $ are orthonormal basis in of $L^2$ $$ \mathbf{\Phi}^T \mathbf{c} = \sum_{i} <f, \phi_i>_{L_2} \phi_i (D) = f(D). $$

I guess there should be a simpler proof than this.