# 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.... – Dougal Jul 9 '18 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? – Wei-Cheng Lee Jul 10 '18 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. – Dougal Jul 10 '18 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. – Wei-Cheng Lee Jul 10 '18 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. – Dougal Jul 10 '18 at 19:55

As shown at 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 eigensystem of $$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 above question.

By substituting the linear combination to 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 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_i(\cdot)$$ $$\lambda_n p_i^{(n)} - \lambda_n \phi_i(D) (k(D,D)+\sigma^2 I)^{-1} \sum_i \lambda_n p_i^{(n)} \phi_i(D)$$ also interchangeability is assumed here.

From now on, we 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_i^{(n)}, p_i^{(n)}, \cdots, ]^T \mathbf{R}^{\aleph_0} \\ \mathbf{\Phi} = [\phi_1(D), \phi_2(D), \cdots, ]^T \in \mathbf{R}^{\aleph_0 \times \vert D \vert}$$ then 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) $$(\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$$

I guess there should be simpler proof than this.