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

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?

• You're right about part 2: the RKHS is exactly the set of functions with finite norm, and if one norm is finite then the other one is too. Thinking about part 1.... Commented Jul 9, 2018 at 13:32
• Thanks you so much. I have another question, are there any kernels such that all the functions in $H_k$ will have bounded norm, if so, how can we compute it? Commented Jul 10, 2018 at 12:14
• No - $H_k$ is a vector space, so for any nonzero $f$ and any $a>0$ then $a f \in H_k$ and $\lVert a f \rVert = a \lVert f \rVert$ can be arbitrarily big. Commented Jul 10, 2018 at 12:17
• That makes me confused. In theory, we often assumed that we know the kernel in advance (it makes sense for me if we choose the universal kernels). But we also make assumption on f that it has bounded RKHS norm and we know the bounded constant B. In reality, there is no way to actually find B since f is black-box. I know that we only care about the cumulative regret bound corresponding to T (iteration) and D(problem dimension) and we can always scale B to sufficiently large. But I think in reality the size of B will need to set very big to accommodate f and thus hurt the speed of convergence. Commented Jul 10, 2018 at 19:36
• $B$ is something like a smoothness constraint. You assume that $f$ is fairly smooth in the sense of this particular kernel, because you have to assume something to do anything and you hope it's more or less true. The less true it is, the slower your algorithm will converge. Commented Jul 10, 2018 at 19:55

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{_{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} = [_{L^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} _{L_2} \phi_i (D) = f(D).$$

I guess there should be a simpler proof than this.