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}$.

- Conjugate symmetry: $\langle \mathbf{x}, \mathbf{y} \rangle = \overline{\langle \mathbf{y}, \mathbf{x} \rangle}$
- 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$
- Positive definiteness: $\langle \mathbf{x}, \mathbf{x} \rangle \ge 0$ where the equality holds only when $\mathbf{x} = 0$.

**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.

Nice work Sadeep! Very clear explanation with good examples.

ReplyDeleteLooking forward to the next part!

Thanks Tao :)

DeleteThank you for writing this. I am also looking forward to the next part!

ReplyDeleteThanks Roemer! I will write the next part as soon as I find some free time.. :)

DeleteThis comment has been removed by the author.

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

ReplyDeleteThanks Charan!

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

ReplyDeleteSo nice article. It is very articulate. Expecting Part III and Part IV.

ReplyDeleteVery, 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!

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

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

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

ReplyDeleteUnless 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!

Hi Gabe,

DeleteThanks 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!

This comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteThanks 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