\( \def\sc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \newcommand{\dee}{\mathrm{d}} \newcommand{\Dee}{\mathrm{D}} \newcommand{\In}{\mathrm{in}} \newcommand{\Out}{\mathrm{out}} \newcommand{\pdf}{\mathrm{pdf}} \newcommand{\Cov}{\mathrm{Cov}} \newcommand{\Var}{\mathrm{Var}} \newcommand{\ve}[1]{\mathbf{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\etal}{{et~al.}} \newcommand{\sphere}{\mathbb{S}^2} \newcommand{\modeint}{\mathcal{M}} \newcommand{\azimint}{\mathcal{N}} \newcommand{\ra}{\rightarrow} \newcommand{\mcal}[1]{\mathcal{#1}} \newcommand{\X}{\mathcal{X}} \newcommand{\Y}{\mathcal{Y}} \newcommand{\Z}{\mathcal{Z}} \newcommand{\x}{\mathbf{x}} \newcommand{\y}{\mathbf{y}} \newcommand{\z}{\mathbf{z}} \newcommand{\tr}{\mathrm{tr}} \newcommand{\sgn}{\mathrm{sgn}} \newcommand{\diag}{\mathrm{diag}} \newcommand{\Real}{\mathbb{R}} \newcommand{\sseq}{\subseteq} \newcommand{\ov}[1]{\overline{#1}} \DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \newcommand{\data}{\mathrm{data}} \newcommand{\N}{\mathcal{N}} \newcommand{\Hil}{\mathcal{H}} \)

A Primer on Reproducing Kernel Hilbert Space Theory

---

1 Hilbert Spaces

• A Hilbert space is a vector space that is
  • equipped with an inner product, and
  • under the norm defined from the inner product, the vector space is complete.
  Here, we denote a Hilbert space with the letter $\Hil$. The inner product and the norm for $\Hil$ are denoted $\langle \cdot, \cdot \rangle_{\Hil}$ and $\| \cdot \|_{\Hil}$, respectively. Moreover, let $0_\Hil$ denote the zero element of $\Hil$ for the sake of distinguishing it from the scalar $0$.
• To refresh your knowledge, see the notes on Hilbert spaces.
• We are particularly interested in functions that maps a set $\mathcal{X} \subseteq \Real^d$ to a real number. So, from now on, $\Hil$ denotes a Hilbert space of such functions. Addition of two functions and multiplying a function by a scalar is defined in the usual way.

2 Reproducing Kernel Hilbert Spaces

• For any two argument function $k(\ve{x}, \ve{x}'): \X \times \X \ra \Real$, we write it as $k_{\ve{x}'}(\ve{x})$ when we want to turn it to a function of $\ve{x}$.
• Definition 2.1. A function $k$ is a reproducing kernel of $\Hil$ if
  • for all $\ve{x'} \in \mathcal{X}$, the function $k_{\ve{x}'}(\ve{x})$ is in $\Hil$;
  • for all $\ve{x'} \in \mathcal{X}$ and for all $f \in \Hil$, we have that \begin{align*} f(\ve{x}') = \langle f, k_{\ve{x}'} \rangle_{\Hil}. \end{align*}
  The second property is called the reproducing property.
• Note that if $k$ is a reproducing kernel of $\ve{x}$, we have that $k(\ve{x}, \ve{x}') = \langle k_{\ve{x}}, k_{\ve{x}'} \rangle_{\Hil}$.
• Since we are only interested in real Hilbert spaces in this note, it follows that any reproducing kernel is symmetric. This is because \begin{align*} k(\ve{x}, \ve{x}') = \langle k_{\ve{x}}, k_{\ve{x}'} \rangle_{\Hil} = \langle k_{\ve{x}', k_{\ve{x}}} \rangle_{\Hil} = k(\ve{x}', \ve{x}) \end{align*} because $\langle k_{\ve{x}}, k_{\ve{x}'} \rangle$ is a real number. If we work in a complex Hilbert space, the kernel would be Hermitian.
• Definition 2.2. If a Hilbert space $\Hil$ has a reproducing kernel, then we called it a reproducing kernel Hilbert space (RKHS).
• Proposition 2.3. For a Hilbert space $\Hil$, if a reproducing kernel exists, it is unique.

  Proof. Let $k$ and $k'$ be reproducing kernels. Then, for any $f \in \Hil$, we have that \begin{align*} \langle f, k_\ve{x} \rangle_\Hil &= \langle f, k'_\ve{x} \rangle_\Hil \\ \langle f, k_\ve{x} - k'_{\ve{x}} \rangle_\Hil &= 0. \end{align*} Using a property of the inner product, this means $k_\ve{x} - k'_{\ve{x}} = 0$, and so $k_\ve{x} = k'_{\ve{x}}$. $\square$

• Definition 2.4. A functional is a real-valued function of a vector space.
• Definition 2.5. Define $\delta_\ve{x}$ to be the evaluation functional at $\ve{x}$. In other words, \begin{align*} \delta_\ve{x} (f) = f(\ve{x}). \end{align*} It should be clear that $\delta_\ve{x}$ is linear.
• Definition 2.6. A functional $F$ is bounded if, for all $f \in \Hil$, there exists a real constant $M > 0$ such that $F(f) \leq M \| f \|_\Hil$.
• By Theorem 5.3 of the Hilbert space note, we have that a linear functional is continuous if and only if it is bounded.
• Theorem 2.6. A Hilbert space of real-valued functions $\Hil$ is an RKHS iff the evaluation functional $\delta_\ve{x}$ is bounded. In other words, for every $\ve{x} \in \X$, there exists a real constant $M_\ve{x} > 0$ such that $$|\delta_{\ve{x}}(f)| = |f(\ve{x})| \leq M_{\ve{x}} \| f\|_\Hil. $$

  Proof. Suppose that there exists a reproducing kernel $k$. Then, $\delta_\ve{x}(f) = f(\ve{x}) = \langle f, k_{\ve{x}} \rangle_\Hil$. Applying the Cauchy-Schwarz inequiality, we have that $|\delta_\ve{x}(f)| = |f(\ve{x})| \leq \| f\|_\Hil \| k_{\ve{x}} \|_\Hil$, so we can choose $M_\ve{x} = \| k_{\ve{x}} \|_\Hil$.

  If the evaluation functional $\delta_\ve{x}$ is bounded, then it is continuous. By the Riesz representation theorem, there is a unique $g_\ve{x} \in H$ such that $\delta_\ve{x}(f) = \langle f, g_\ve{x} \rangle_\Hil$. Define $k(\ve{x}', \ve{x}) = g_{\ve{x}}(\ve{x}')$. It is clear that $k_\ve{x} = g_\ve{x} \in \Hil$. As a result, $k$ is a reproducing kernel of $\Hil$. $\square$

• Lemma 2.6. Let $\Hil$ be an RKHS, and let $f, g \in \Hil$. If $\| f - g\|_{\Hil} = 0$, then $f$ and $g$ agree at all points.

  Proof. We have that, for all $\ve{x} \in \mathcal{X}$, \begin{align*} \| f(\ve{x}) - g(\ve{x}) \| = |\delta_{\ve{x}}(f-g)| \leq c_\ve{x} \| f - g \|_{\Hil} = 0. \end{align*} As a result, $f(\ve{x}) = g(\ve{x})$. $\square$

3 Positive Definite Kernels and RKHS

• Definition 3.1. We call $k(\ve{x}, \ve{x}'): \mathcal{X} \times \mathcal{X} \rightarrow \Real$ a positive definite kernel if (1) $k$ is a symmetric function: \begin{align*} k(\ve{x}, \ve{x}') = k(\ve{x}', \ve{x}) \end{align*} for all $\ve{x}, \ve{x}' \in \mathcal{X}$, and (2): \begin{align*} \sum_{i=1}^n \sum_{j=1}^n c_i c_j k(\ve{x}_i, \ve{x}_j) \geq 0 \end{align*} for any $\ve{x}_1, \ve{x}_2, \dotsc, \ve{x}_n \in \mathcal{X}$ and $c_1, c_2, \dotsc c_n \in \Real$. In other words, the matrix \begin{align*} \begin{bmatrix} k(\ve{x}_1, \ve{x}_1) & k(\ve{x}_1, \ve{x}_2) & \cdots & k(\ve{x}_1, \ve{x}_n) \\ k(\ve{x}_2, \ve{x}_1) & k(\ve{x}_2, \ve{x}_2) & \cdots & k(\ve{x}_2, \ve{x}_n) \\ \vdots & \vdots & \ddots & \vdots \\ k(\ve{x}_n, \ve{x}_1) & k(\ve{x}_n, \ve{x}_2) & \cdots & k(\ve{x}_n, \ve{x}_n) \end{bmatrix} \end{align*} is positive definite for all $\ve{x}_1, \ve{x}_2, \dotsc, \ve{x}_n \in \mathcal{X}$.
• Proposition 3.2. Let $k: \X \times \X \ra \Real$. If there is an inner product space $V$ and a function $\phi: \X \ra V$ such that $k(\ve{x}, \ve{x}') = \langle \phi(\ve{x}), \phi(\ve{x}') \rangle_V$, then $k$ is positive definite.

  Proof. We have that \begin{align*} \sum_{i=1}^n \sum_{j=1}^n c_i c_j k(\ve{x}_j, \ve{x}_n) &= \sum_{i=1}^n \sum_{j=1}^n c_i c_j \langle \phi(\ve{x}_i), \phi(\ve{x}_j) \rangle_V \\ &= \sum_{i=1}^n \sum_{j=1}^n \langle c_i \phi(\ve{x}_i), c_j \phi(\ve{x}_j) \rangle_V \\ &= \bigg\langle \sum_{i=1}^n c_i \phi(\ve{x}_i), \sum_{i=1}^n c_j \phi(\ve{x}_j) \bigg\rangle_V \\ &= \bigg\langle \sum_{i=1}^n c_i \phi(\ve{x}_i), \sum_{i=1}^n c_i \phi(\ve{x}_i) \bigg\rangle_V \\ &= \bigg\| \sum_{i=1}^n c_i \phi(\ve{x}_i) \bigg\|^2_V \\ &\geq 0. \end{align*} So, $k$ is positive definite. $\square$

• Theorem 3.3. For any RKHS, its reproducing kernel is positive definite.

  Proof. We have that $k(\ve{x}, \ve{x}') = \langle k_{\ve{x}}, k_{\ve{x}'} \rangle_{\Hil}$. So, we can set $\phi(\ve{x}) = k_{\ve{x}}$.

• Theorem 3.4 (Moore-Aronszajn). Let $k: \X \times \X \ra \Real$ be positive definite. There is a unique RKHS $\Hil \subseteq \Real^\X$ with $k$ as the reproducing kernel. In particular, it is the closure of the linear span \begin{align*} \bigg\{ f : f(\ve{x}) = \sum_{i=1}^m a_i k(\ve{x}, \ve{x}_i), a_i \in \Real, m \in \mathbb{N}, \ve{x}_i \in \mathcal{X} \bigg\}. \end{align*} The inner product is defined as \begin{align*} \langle f, g \rangle_{\Hil} = \sum_{i,j} a_i b_j k(\ve{x}_i, \ve{x}_j) \end{align*} where $f(\ve{x}) = \sum_i a_i k(\ve{x}, \ve{x}_i)$ and $g(\ve{x}) = \sum_j b_j k(\ve{x}, \ve{x}_j)$. In other words, this is the set of functions that can be written as a kernel density estimation of a finite set of points and their limit functions.
• Note. I'm too lazy to complete the proof. I might return to this later.

4 Construction from Spectral Decomposition

• Let $k$ be a positive definite kernel. By Mercer's theorem, there exists eigenfunctions $\{ e_j \}_{j=1}^\infty$ and positive eigenvalues $\{\lambda_j \}_{j=1}^\infty$ such that: \begin{align*} k(\ve{x}, \ve{x}') = \sum_{j=1}^\infty \lambda_j e_j(\ve{x}) e_j(\ve{x}'). \end{align*} Note that the eigenfunctions are orthogonal. In other words, \begin{align*} \int_{\mathcal{X}} e_i(\ve{x}) e_j(\ve{x})\, \dee\ve{x} = \begin{cases} 1, & i = j \\ 0, & i \neq j \end{cases}. \end{align*}
• Definition 4.1. From the positive definite kernel $k$, we can define a Hilbert space of functions as follows: \begin{align*} \Hil = \bigg\{ \sum_{j=1}^\infty f_j e_j : \sum_{j=1}^\infty \frac{f_j^2}{\lambda_j} < \infty \bigg\}. \end{align*} Given $f = \sum_j f_j e_j$ and $g = \sum_j g_j e_j$, define the dot product as: \begin{align*} \langle f, g \rangle_\Hil = \sum_{j=1}^\infty \frac{f_j g_j}{\lambda_j}. \end{align*} The induced norm is given by \begin{align*} \| f \|_\Hil = (\langle f, f\rangle_\Hil)^{1/2} = \bigg( \sum_{j=1}^\infty \frac{f_j^2}{\lambda_j} \bigg)^{1/2}. \end{align*}
• Note that one can prove that the inner product is well-defined, the space is closed under addition and multiplication by scalar, and that the space is complete using the same arguments that are used to prove that the space $\ell^2$ is a Hilbert space. See Section 3.1 of the Hilbert space note for details.
• Proposition 4.2. With $\Hil$ defined above, $k$ is a reproducing kernel of $\Hil$.

  Proof. Let $f = \sum_{i=1}^\infty f_i e_i \in \Hil$. We have that \begin{align*} k_{\ve{x}} = \sum_{j=1}^\infty \lambda_k e_j(\ve{x}) e_j \end{align*} Hence, \begin{align*} \langle f, k_\ve{x} \rangle = \sum_{j=1}^\infty \frac{f_j \lambda_j e_j(\ve{x})}{\lambda_j} = \sum_{j=1}^\infty f_j e_j(\ve{x}) = f(\ve{x}). \end{align*} So, $k$ is a reproducing kernel. $\square$

---

Last modified: 2020/08/07