RKHS norm and Fourier transform link

Question

In the notes here, it is stated that norms of some reproducing kernel Hilbert spaces can be written in terms of Fourier transforms, and this is often used to argue that a higher RKHS norm implies a less smooth function.

For example, the Gaussian kernel is defined as: $$ k(x_i, x_j) = \exp \left ( {\frac{\|x_i - x_j \|^2}{\sigma^2}} \right ) $$ for all $x_i, x_j$ belonging to some set $X \subset \mathbb{R}^d$, and $\sigma > 0$ is a tuning parameter. The RKHS corresponding to this kernel, denoted $H_k$ has elements defined as: $$ f(\cdot) := \sum_{i=1}^{\infty} {\alpha_i} k(\cdot, x_i) $$ and corresponding norm: $$ \| f \|_{H_k} := \sum_{i=1}^{\infty }\sum_{j=1}^{\infty } \alpha_i \alpha_j k(x_i, x_j) = \sum_{i=1}^{\infty }\sum_{j=1}^{\infty } \alpha_i \alpha_j \exp \left ( {\frac{\|x_i - x_j \|^2}{\sigma^2}} \right ). $$

But the linked notes say that we can write: $$ \| f \|_{H_k} = \frac{1}{2 \pi^d} \int |F(\omega)|^2 e^\frac{{\sigma^2 \omega^2}}{2} d \omega $$ where $F(\omega)= \int_{-\infty}^{\infty} f(t) e^{-i \omega t} dt$, but I can't really find a proof of this anywhere. Does anyone know where I can find one or can provide an outline here?

Answer 1

I'm also learning this stuff and was unable to find a proof so I took a swing at one.

There's a couple things we need to know about RKHS and Fourier analysis before we start (that I think are well established online if you're unfamiliar):

1. The word "reproducing" in RKHS comes from the fact that if we take the inner product of some function $f \in \mathcal{H}$ (where $\mathcal{H}$ is our RKHS) with a kernel function centered at $\mathbf{x}$, that's the same thing as evaluting our function at $\mathbf{x}$: $\langle f, k(.,\mathbf{x})\rangle = f(\mathbf{x})$.

2. If $h(\mathbf{x}) = f(\mathbf{x} - \mathbf{x}_0)$, then $\hat{h}(\mathbf{t}) = e^{-2\pi i \mathbf{x}_0^\top\mathbf{t}} \hat{f}(\mathbf{t})$, so the Fourier transforms of a function and a shifted version of that function are related.

I'm going to do this proof in the context of a general stationary covariance function $k$, but it would be straightforward to plug in your Gaussian kernel if you are exclusively interested in that. Since it's stationary, our kernel function may be expressed as $k(\mathbf{x}, \mathbf{y}) = d(\mathbf{x}-\mathbf{y})$ for some function $d$ ($d(\mathbf{x}) = e^{-\frac{||\mathbf{x}||_2^2}{\sigma^2}} $in the Gaussian case).

We want to show the following:

$ \langle f, g \rangle_{\mathcal{C}} := \int_{\mathbb{R}^d} \frac{\hat{f}(\mathbf{t}) \overline{\hat{g}(\mathbf{t})}}{\hat{d}(\mathbf{t})} d\mathbf{t} =\langle f, g \rangle_{\mathcal{H}} \,\,\,\,\, \forall f,g \in \mathcal{H}$

or, in words, that our candidate inner product $ \langle f, g \rangle_{\mathcal{C}}$ agrees with our actual RKHS inner product $\langle f, g \rangle_{\mathcal{H}}$ for all possible $f, g \in \mathcal{H}$ (the result you ask about regarding $||f||_\mathcal{H}$ follows immediately from this result about the inner product).

The strategy for the proof will be to take our candidate inner product $\langle f, g \rangle_{\mathcal{C}}$ and show that it satisfies the reproducing property, that is, that $\langle f, k(.,\mathbf{x}) \rangle_{\mathcal{C}} = f(\mathbf{x})$, and then to expand on this to show that the inner products agree no matter which 2 functions we want to compute it between.

To this end, we will examine the quantity:

$ \langle f, k(., \mathbf{x}) \rangle_{\mathcal{C}} = \int_{\mathbb{R}^d} \frac{\hat{f}(\mathbf{t}) \overline{\hat{k(.,\mathbf{x})}(\mathbf{t})}}{\hat{d}(\mathbf{t})} d\mathbf{t}$

To proceed, let us evaluate $\hat{k(.,\mathbf{x})}(\mathbf{t})$. Since $k$ is stationary, $k(\mathbf{y}, \mathbf{x})=d(\mathbf{y}-\mathbf{x})$, and given fact (2) above, we thus know that $\hat{k(.,\mathbf{x})}(\mathbf{t}) = e^{-2\pi i \mathbf{x}^\top\mathbf{t}} \hat{d}(\mathbf{t})$. Substitution yields:

$ \langle f, k(., \mathbf{x}) \rangle_{\mathcal{C}} = \int_{\mathbb{R}^d} \frac{\hat{f}(\mathbf{t}) \overline{e^{-2\pi i \mathbf{x}^\top\mathbf{t}} \hat{d}(\mathbf{t})}}{\hat{d}(\mathbf{t})} d\mathbf{t}$

Since $d$ is real and symmetric, $\overline{\hat{d}(\mathbf{t})} = \hat{d}(\mathbf{t})$, and we have:

$ \langle f, k(., \mathbf{x}) \rangle_{\mathcal{C}} = \int_{\mathbb{R}^d} \frac{\hat{f}(\mathbf{t}) e^{2\pi i \mathbf{x}^\top\mathbf{t}} \hat{d}(\mathbf{t})}{\hat{d}(\mathbf{t})} d\mathbf{t} = \int_{\mathbb{R}^d} \hat{f}(\mathbf{t})e^{2\pi i \mathbf{x}^\top\mathbf{t}} d\mathbf{t} = f(\mathbf{x}) = \langle f, k(.,\mathbf{x})\rangle_{\mathcal{H}}$

since this is the inverse of the Fourier Transform (notice the negative sign in the exponential term cancelled with complex conjugation). So we've shown that the inner product is the same when the first argument is a function and the second a kernel. Now to generalize.

Consider:

$ \langle f, g \rangle_{\mathcal{C}} = \langle f, \sum_{i} a_i k(.,\mathbf{x}_i)\rangle_{\mathcal{C}} = \sum_{i} a_i \langle f, k(.,\mathbf{x}_i)\rangle_{\mathcal{C}} = \sum_{i} a_i \langle f, k(.,\mathbf{x}_i)\rangle_{\mathcal{H}} = \langle f, \sum_{i} a_i k(.,\mathbf{x}_i)\rangle_{\mathcal{H}} = \langle f, g \rangle_{\mathcal{H}} $

which establishes that the inner product agrees for all $f,g$. To establish the result you were interested in, explicitly plug in the form of the Gaussian kernel's Fourier transform, and examine the inner product between a function and itself.