Friday, September 27, 2013

A Tutorial Introduction to Reproducing Kernel Hilbert Spaces - Part II


In the present article, we continue the tutorial on Reproducing Kernel Hilbert Spaces (RKHS). The previous part of this tutorial can be found here.

We start this article with a quick summary of the various spaces we introduced in the previous post. This summary is only supposed to give you some intuitive ideas about these different spaces. For rigorous definitions and more explanations, please refer to the previous post.

  • Vector space - A set endowed with two special operations: addition and scalar multiplication.
  • Normed vector space - A vector space with length of vectors defined. This notion of vector lengths also allows us to measure distances between vectors.
  • Metric space - A set (nor necessarily a vector space) where the distance between two points in the set is defined. A normed vector space is a metric space. But the converse is not true.
  • Banach space - A complete normed vector space. A complete space does not have missing elements (all Cauchy sequences have limits).

When we introduced normed vector spaces, we introduced an important structure on vector spaces: distance. Now, we would like to introduce another structure on vector spaces which is inner product. Note that, inner product is different from scalar product that any vector space possesses. The scalar product of a vector space operates on a scalar and a vector, yielding a vector as the output. In contrast, an inner product works on two vectors, giving a scalar as the output. When an inner product is defined on a vector space, it is known as as an inner product space. We now proceed to the formal definition.

Inner Product Space

An inner product space, $(\mathcal{V}, \langle., .\rangle)$ is a vector space $\mathcal{V}$ over a field $\mathbb{F}$ with a binary operator $\langle., .\rangle : \mathcal{V}\times \mathcal{V} \to \mathbb{F}$, known as the inner product, that satisfies the following axioms for all vectors $\mathbf{x}, \mathbf{y}, \mathbf{z} \in \mathcal{V}$ and all scalars $a \in \mathbb{F}$.
  1. Conjugate symmetry: $\langle \mathbf{x}, \mathbf{y} \rangle = \overline{\langle \mathbf{y}, \mathbf{x} \rangle}$
  2. Linearity in the first argument: $\langle a\mathbf{x}, \mathbf{y} \rangle = a \langle \mathbf{x}, \mathbf{y} \rangle$ and $\langle \mathbf{x} + \mathbf{z}, \mathbf{y} \rangle = \langle \mathbf{x}, \mathbf{y} \rangle + \langle \mathbf{z}, \mathbf{y} \rangle$
  3. Positive definiteness:  $\langle \mathbf{x}, \mathbf{x} \rangle \ge 0$ where the equality holds only when $\mathbf{x} = 0$.
The field $\mathbb{F}$ is either the field or real numbers ($\mathbb{R}$) or the field of complex numbers ($\mathbb{C}$). When $\mathbb{F}$ is the real numbers, axiom 1 implies symmetry since the conjugate of a real number is itself.

Exercise 1: The dot product of the $n$-dimensional Euclidean space $\mathbb{R}^n$ is defined as $\mathbf{x}.\mathbf{y} = \sum_{i = 1}^n x_i y_i$ where $x_i, y_i$, $i = 1,\ldots,n$, are the components of vectors $\mathbf{x}$, $\mathbf{y}$, respectively. Show that $\mathbb{R}^n$, endowed with the dot product, is an inner product space.

Exercise 2: Let $\mathcal{F}$ be the set of real valued, square-integrable functions. i.e.,
\[
\mathcal{F} = \{f | f: \mathbb{R} \to \mathbb{R}, \int_{-\infty}^\infty |f(x)|^2 dx < \infty \}.
\]
It is known that $\mathcal{F}$ forms an infinite dimensional vector space over the field $\mathbb{R}$ with the usual function addition and scalar multiplication. Show that $\mathcal{F}$ is also an inner product space where the inner product $\langle ., . \rangle: \mathcal{F} \times \mathcal{F} \to \mathbb{R}$ is defined for all $f, g \in \mathcal{F}$ as:

\[
\langle f, g \rangle = \int_{-\infty}^\infty f(x)g(x) dx < \infty.
\]
Note that in Exercise 2 above, vectors of the vector space $\mathcal{F}$ are actually functions. To help visualization of functions as vectors, one can assume that all functions in the vector space are sampled at $n$ fixed points $x_1, \ldots, x_n$ equally spaced in the domain of the functions (the real line in the above case). Then, a given function $f$, can be represented (not uniquely) by an $n$-vector $[f(x_1)\;\;f(x_2)\;\;\ldots\;\;f(x_n)]$ lying in the $n$-dimensional vector space $\mathbb{R}^n$. When $n \to \infty$, these functions form an infinite dimensional vector space.

The reader is encouraged to attempt the following simple exercise now.

Exercise 3: Let $(\mathcal{V}, \langle ., . \rangle_\mathcal{V})$ be an inner product space. Show, starting from the definitions of an inner product space and a normed vector space, that $(\mathcal{V}, \| . \|_\mathcal{V})$ where $\|\mathbf{x}\|_\mathcal{V} = \sqrt{\langle \mathbf{x}, \mathbf{x} \rangle_\mathcal{V}}$ for all $\mathbf{x} \in \mathcal{V}$, is a normed vector space.

As seen from the above exercise, when we have the inner product structure on a vector space, we can also define a norm on the space with the help of the inner product. This norm, known as the $l^2$ norm, is defined by:$\|\mathbf{x}\|  = \sqrt{\langle x, x \rangle}$ where $\mathbf{x}$ is a vector in the inner product space with inner product $\langle ., . \rangle$. As a specific example, when the inner product space is $\mathbb{R}^n$ with the usual dot product as the inner product, for all $\mathbf{x} \in \mathbb{R}^n$, $\|\mathbf{x}\|  = \sqrt{x.x} = \sum_{i = 1}^n x_i^2$.

Although an inner product induces a norm, not every norm is induced by an inner product. For example, the $l^1$ norm, defined on $\mathbb{R}^n$ by $\|\mathbf{x}\|_{1} = \sum_{i = 1}^n |x_i|$, is not induced by an inner product.

An inner product space is also known as a pre-Hilbert space, meaning that it is one step behind a Hilbert space, which is our next subtopic.

Hilbert Space

As discussed above, an inner product space has a norm induced by its inner product. However, a generic inner product space might not be complete with respect to this norm (recall the definition of completeness from the previous post). When this condition is satisfied, i.e., when an inner product space is complete with respect to the norm induced by its inner product, it is known as a Hilbert space. An example for a Hilbert space would be $\mathbb{R}^n$ with the usual dot product.

It is easy to see that a Hilbert space with its canonical norm (the norm induced by the inner product) is also a Banach space. Although, a Hilbert space does not necessarily have to be infinite dimensional, the term Hilbert space usually implies an infinite dimensional space such as a space of functions. An example for an infinite dimensional Hilbert space would be the space of square-integrable functions introduced in Exercise 2. It is known as the $L^2$ space.

Reproducing Kernel Hilbert Space

We have now reached the main topic of this tutorial. We will start the topic by defining some of the terms we will be using. Since these definitions are quite straightforward and easy to understand, we directly present them below without further discussion.

Linear operator (Linear map) - Let $f:\mathcal{V}\to \mathcal{W}$ be a function between two vector spaces $\mathcal{V}, \mathcal{W}$ over the same field $\mathbb{F}$. $f$ is called a linear operator if the following two conditions are satisfied for all $\mathbf{x}, \mathbf{y} \in \mathcal{V}$ and $a \in \mathbb{F}$.
1. $f(\mathbf{u} + \mathbf{v}) = f(\mathbf{u}) + f(\mathbf{v})$
2. $f(a\mathbf{u}) = af(\mathbf{u})$

Bounded linear operator -  Let $f:\mathcal{V}\to \mathcal{W}$ be a linear operator between two normed vector spaces $(\mathcal{V}, \|.\|_\mathcal{V})$ and $(\mathcal{W}, \|.\|_\mathcal{W})$. $f$ is called a bounded linear operator if there exists some $M > 0$ such that for all $\mathbf{u} \in \mathcal{V}$, $\|f(\mathbf{u})\|_{\mathcal{W}} \le M\|\mathbf{u}\|_{\mathcal{V}}$.

The next article will be dedicated to discussing Reproducing Kernel Hilbert Spaces (RKHS) and their properties.

17 comments:

  1. Nice work Sadeep! Very clear explanation with good examples.

    Looking forward to the next part!

    ReplyDelete
  2. Thank you for writing this. I am also looking forward to the next part!

    ReplyDelete
    Replies
    1. Thanks Roemer! I will write the next part as soon as I find some free time.. :)

      Delete
  3. This comment has been removed by the author.

    ReplyDelete
  4. Sadeep, thanks for the very useful overview of functional spaces, looking forward for the final part on RKHS ...

    ReplyDelete
  5. Thanks for the useful articles. Could you kindly let me know the link for Part III and Part IV, etc?

    ReplyDelete
  6. So nice article. It is very articulate. Expecting Part III and Part IV.

    ReplyDelete
  7. Very, very nicely written summary and interpretation of the foundations of RKHS (one of the cleasest expositions I have ever read) , but where is the promised article on RKHS itself? Your readers are waiting!

    ReplyDelete
  8. Thanks guys! Other parts are coming along. I have been bit busy with my thesis, hence the delay.

    ReplyDelete
  9. Hi all, the next article of this series is now published at http://sadeepj.blogspot.com.au/2014/05/a-tutorial-introduction-to-reproducing.html.

    ReplyDelete
  10. Thanks sadeep, great article. Minor note: I believe your definition of the positive-definite property should be >= 0, rather than >= 0.

    Unless I'm missing something, by the written definition, R^n would not be an inner-product space, since the dot-product of any vector with only positive components and a vector with only negative components would be negative.

    Probably just a type-o, but it tripped me up for a minute.
    Thanks!

    ReplyDelete
    Replies
    1. Hi Gabe,

      Thanks for pointing this out. There was indeed a typo there, I just corrected it. It should be >= 0 (inner product of a vector with itself should be non-negative). Both R^n and C^n are inner product spaces with the usual dot product as the inner product. Apologies about the confusion.

      Thanks!

      Delete
  11. This comment has been removed by the author.

    ReplyDelete
  12. This comment has been removed by the author.

    ReplyDelete
  13. Thanks sadeep, great article. There was a typo there. when the inner product space is R^n with the usual dot product as the inner product, for all x∈R^n, ||x||=sqrt(x.x)=sqrt(∑xi2).

    ReplyDelete