A Tutorial Introduction to Reproducing Kernel Hilbert Spaces - Part I

In this post we will study different spaces encountered in Linear Algebra and Functional Analysis. Our final goal is to understand what is meant by Reproducing Kernel Hilbert Spaces or RKHS which have a wide range of applications in machine learning and related fields. We begin with vector spaces, which any engineering undergraduate student is familiar with.

Vector Space

In simple terms, a vector space is a set whose elements have two characteristic properties:

1) Two elements can be added to obtain an element in the same set.

2) A given element can be multiplied by a scalar to obtain an element in the same set.

Elements of such a set are dubbed vectors. Perhaps, the simplest example of a vector space is $\mathbb{R}^3$ with elements of $\mathbb{R}$ as scalars. Addition and multiplication in this vector space can be demonstrated as follows.

\[\text{Addition:}\hspace{1cm} \begin{bmatrix} 1 \\ 2 \\ 3 \\ \end{bmatrix} + \begin{bmatrix} 4 \\ 5 \\ 6 \\ \end{bmatrix} = \begin{bmatrix} 5 \\ 7 \\ 9 \\ \end{bmatrix} \hspace{3cm} \text{Scalar Multiplication:} \hspace{1cm} 0.2 \begin{bmatrix} 9 \\ 8 \\ 7 \\ \end{bmatrix} = \begin{bmatrix} 1.8 \\ 1.6 \\ 1.4 \\ \end{bmatrix} \]

Formally, a vector space over a field $\mathbb{F}$ is a set $\mathcal{V}$ with two binary operations: addition (denoted by $+$) and scalar multiplication (denoted by $.$ or by writing two objects close to each other), that satisfy number of axioms for all $a, b \in \mathbb{F}$ and $\mathbf{u}, \mathbf{v} \in \mathcal{V}$. We omit these axioms here for the sake of brevity. Virtually in all cases $\mathbb{F}$ is either the field of real numbers ($\mathbb{R}$) or complex numbers ($\mathbb{C}$).

As you may have already noted, we use simple letters ($a, b, $ etc.) to denote elements of $\mathbb{F}$, known as scalars and boldface letters ($\mathbf{u}, \mathbf{v}$, etc.) to denote elements of $\mathcal{V}$, known as vectors. Hereafter, we may use $\mathcal{V}$ to denote a vector space without explicit reference to the field or the two operations.

Vector space introduces a very rich structure for a set. However, to perform mathematical analysis on a vector space, we need additional tools on the vector space such as a vector lengths, distance between vectors and angle measures. Note that a plain vector space lacks all these ideas. We shall first consider the notion of length of a vector in a vector space.

Normed Vector Space

Simply put, a normed vector space is a vector space whose vectors have lengths. The length or the norm of a vector $\mathbf{v}$ is denoted by $\|\mathbf{v}\|$. The norm has to satisfy several axioms as formalized by the following definition of a normed vector space.

Definition (Normed Vector Space):

A normed vector space $(\mathcal{V}, \|.\|)$, is a vector space $\mathcal{V}$ over a field $\mathbb{F}$, endowed with a norm, $\|.\| : \mathcal{V} \to \mathbb{R}$ that satisfies following axioms for all $\mathbf{v} \in \mathcal{V}$ and $a \in \mathbb{F}$.

1. $\|\mathbf{v}\| \ge 0$.
2. $\|\mathbf{v}\| = 0$ if and only if $\mathbf{v} = \mathbf{0}$.
3. $\|a\mathbf{v}\| = |a| \|\mathbf{v}\|$.
4. $\|\mathbf{u} + \mathbf{v}\| \le \|\mathbf{u}\| + \|\mathbf{v}\|$.

Defining a norm on a vector space enables us to measure distance between vectors in the space. Distance between two vectors $\mathbf{u}, \mathbf{v} \in \mathcal{V}$ is equal to the the length of $\mathbf{u} - \mathbf{v}$ ¹. Formally, $d(\mathbf{u}, \mathbf{v}) = \|\mathbf{u} - \mathbf{v}\|$ where $d(., .)$ is the distance function.

In fact, the distance between points can be defined on any nonempty set which is not necessarily a vector space. A set with a distance measure between its elements is known as a metric space. We now present the formal definition of a metric space.

Metric Space

Definition (Metric Space):

A metric space $(M, d)$ is a set $M$ along with a function $d : M \times M \to \mathbb{R}$ that satisfies following axioms for all $x, y, z \in M$.

1. $d(x, y) \ge 0$.
2. $d(x, y) = 0$ if and only if $x = y$.
3. $d(x, y) = d(y, x)$.
4. $d(x, z) \le d(x,y) + d(y, z)$.

The function $d$ that satisfies above axioms is known as the metric or the distance function. The last axiom (or property when it's satisfied by a metric), known as the triangle inequality, is perhaps the most interesting property of a metric.

Every normed vector space is a metric space. But the converse is not true; we don't require a vector space structure on a set to define a valid metric on it.

Banach Space

A Banach space is a complete normed vector space. What exactly is completeness? To define completeness, we first need to understand what is meant by a Cauchy sequence.

Cauchy Sequence

A Cauchy sequence is a sequence of elements from a set where nearby elements get increasingly close to each other (see Figure 1). For the above sentence to make sense, we need a way to measure the closeness (or the distance) between two elements of the set. Hence, Cauchy sequences are defined on metric spaces. Below we give the definition of a Cauchy sequence in a normed vector space and a more general metric space. The reader can easily see that the first definition is just a special case of the second.

Definition (Cauchy Sequence):

Normed Vector Space: In a normed vector space $(\mathcal{V}, \|.\|)$ a sequence of vectors $\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3,\ldots$ is called a Cauchy sequence if for all $\varepsilon > 0$, there exists an $N \in \mathbb{Z}^+$ such that, for all $n, m > N$, $\|\mathbf{x}_n - \mathbf{x}_m\| < \varepsilon$.

Metric Space: In a metric space $(M, d)$, a sequence $x_1, x_2, x_3, \ldots$ where $x_i \in M$ for $i = 1,2,3,\ldots$ is called a Cauchy sequence if for all $\varepsilon > 0$, there exists an $N \in \mathbb{Z}^+$ such that, for all $n, m > N$, $d(x_n, x_m) < \varepsilon$.

Intuitively, a Cauchy sequence is a sequence that converges or has a limit as $n$ goes to infinity. However, for some spaces and for some Cauchy sequences, this limit might not be an element of the space on which the sequence is defined. Therefore, such a limit does not exist, and the Cauchy sequence does not converge.

Figure 1. A Cauchy sequence on $\mathbb{R}$. As $n$ grows, $x_n$ s become arbitrary close to each other and to the limit of the sequence (1 in this case).

Completeness

A metric space is called complete if every Cauchy sequence defined on it is convergent, i.e., every Cauchy sequence has a limit which is a point in the same space. It's worth noting again that we must have a metric defined on the space to talk about Cauchy sequences and hence about completeness. Therefore, the completeness is always defined with respect to a metric.

Example

An example for a complete space is $\mathbb{R}^n$ with respect to the usual distance measure (Euclidean distance). Let's consider $\mathbb{R}$, to be more specific. Euclidean distance narrows down to absolute value in this case. Every Cauchy sequence defined on $\mathbb{R}$ with respect to this metric converges to an element of $\mathbb{R}$, hence $\mathbb{R}$ is complete. 

Non-Example

Consider the set of rational numbers, $\mathbb{Q}$ with absolute value as the metric. The sequence defined recursively on $\mathbb{Q}$ as $x_1 = 1$, $x_n = x_n/2 + 1/x_n$ is Cauchy but does not have a limit in $\mathbb{Q}$. In fact, if the same sequence is defined on $\mathbb{R}$, its limit is identified as $\sqrt{2}$ which is not an element of $\mathbb{Q}$.

Now, coming back to the definition of a Banach space, we understand that a Banach space is a normed vector space where all Cauchy sequences converge (or equivalently, have limits). We can think of an incomplete space as a space with holes. A complete space, on the other hand, does not have any holes. Completing a space (something we will encounter shortly), is similar to filling holes in the space by adding missing elements to it.

In the next article we shall continue the tutorial to discuss inner product spaces, Hilbert spaces and Reproducing Kernel Hilbert Spaces.

---

1 Subtraction $-$ in a vector space is defined as $\mathbf{u} - \mathbf{v} := \mathbf{u} + (-\mathbf{v})$ where $-\mathbf{v}$ is the additive inverse of $\mathbf{v}$^↩

Understanding Riemannian Manifolds Part I: Quick Introduction to Topology

Topological Spaces

The $n$-dimensional Euclidean space, \(\mathbb{R}^n\), is the richest space that we know of. Notions of distance, norm, inner product etc. are understood in \(\mathbb{R}^n\). Moreover, limits, continuity and differentiability are well defined on it. We would like to see how these concepts (or more abstract versions of them) could be generalized to other spaces that are not as rich as Euclidean spaces. Topological spaces are the most abstract kind of such spaces. We shall begin the discussion on Riemannian manifolds by defining topological spaces.

Definition 1.1: Topological space

A set \(X\) together with a collections of its subsets \(T\), usually denoted by $(X, T)$, is known as a topological space if the following axioms are satisfied.

1. \(X\) and \(\phi\) are included in \(T\).
2. Any union of sets in \(T\) is included in \(T\).
3. Any finite intersection of sets in \(T\) is included in \(T\).

In such cases, sets in \(T\) are named as open sets and $T$ itself is referred to as a topology of X. An open neighborhood of a point \(x\) \(\in\) \(X\) is any open set containing \(x\). In this series of articles we use the terms neighborhood and open neighborhood interchangeably to mean the same. 

Example

$(X, T)$ with \(X = \{1, 2, 3\}, T = \{\{1,2,3\}, \phi, \{2, 3\}, \{2\}, \{3\}\}\) is a topological space since all the three axioms are satisfied. Some tests are shown below.

\(\{2\} \in T\) and \(\{2, 3\} \in T\), 

1. \(\{2\} \cup \{2, 3\} = \{2, 3\}\) is also in \(T\) (Axiom 2)
2. \(\{2\} \cap \{2, 3\} = \{2\}\) is also in \(T\) (Axiom 3)

Similarly, the reader can verify the same for other unions and finite intersections of sets in \(T\). In this example \(\{1, 2, 3\}, \{2, 3\}\) and \(\{2\}\) are open neighborhoods of 2 \(\in\) \(X\).

Non-Example

$(X, T)$ with \(X = \{1, 2, 3\}, T = \{\{1,2,3\}, \phi, \{1, 2\}, \{2, 3\}\}\) is not a topological space. Because, for \(\{1, 2\}, \{2, 3\} \in T\), their intersection, \(\{1, 2\} \cap \{2, 3\} = \{2\}\) is not in \(T\).

From now on we may refer to a set \(X\) as a topological space without explicit reference to its topology \(T\). In such references it is implied that a valid topology is defined on \(X\). 

Euclidean Topology and Metric Topology

In order to understand the rather abstract notion of a topological space presented in the previous section, let us now consider a particular concrete example of a topological space. We pick the $n$-dimensional Euclidean space, $\mathbb{R}^n$. As understood from the previous section, in order to define a topological space, we need to identify a set ($X$) and a collection of subsets ($T$) that are closed under union and finite intersection. 'Open sets' is a name given to members of $T$. In the present example, $X$ is the infinite set that consists of all $n$-dimensional vectors in $\mathbb{R}^n$. What is $T$ then?

In order to define $T$, we first define open sets on $\mathbb{R}^n$ such that the axioms in Definition 1.1 are satisfied. Then, all $n$-dimensional vectors together with the collection of such defined open sets will form a topological space.

We now proceed to defining an open set in $\mathbb{R^n}$. We start with the definition of an open ball.

Definition 1.2: Open ball (Euclidean spaces)

For any \(x_0 \in \mathbb{R}^n\) and $\varepsilon > 0$, the open ball of radius $\varepsilon$ around $x_0$ is the set \(B_{\varepsilon}(x_0) = \{x \in \mathbb{R}^n \mid \|x - x_0\| < \varepsilon \}\).

An open ball around a point \(x_0 \in \mathbb{R}^2 \) is graphically shown in Figure 1. Radius of the ball, $\varepsilon$, can be arbitrarily small. The intuition is, an open ball contains all points that are sufficiently close to the given point. How do we define 'closeness'? Well, we use the concept of distance between two points in \(\mathbb{R}^n\).

Figure 1: An open ball in \(\mathbb{R}^2\). Note that the circumference of the circle is not included in the 'open' ball.

It's worth noting that this definition of an open ball depends only on the notion of distance between two points i.e., \(\| x - x_0 \| \). In Euclidean spaces, we measure the distance between any two points by taking the vector norm of the difference vector. This is known as Euclidean distance or Euclidean metric. It is not necessary to have a Euclidean space (or any normed vector space for that matter) to measure the distance between two points. In fact, the notion of distance between any two points is present in a more general metric space. While discussing about $\mathbb{R}^n$ we would like to extend the concepts to this more general structure.

Simply put, a metric space is a set with the notion of distance between two points. A metric space is usually denoted by $(M, d)$ where $M$ is the set and $d$ is the distance function or the metric. Any $n$-dimensional Euclidean space, along with the Euclidean distance, forms a metric space.

The following definition of an open ball in a metric space is a direct generalization of the above definition for Euclidean spaces.

Definition 1.3: Open ball (Metric space)

Let $(M, d)$ be a metric space. For any \(x_0 \in M\) and $\varepsilon > 0$, the open ball of radius $\varepsilon$ around $x_0$ is the set \(B_{\varepsilon}(x_0) = \{x \in M \mid d(x, x_0) < \varepsilon \}\).

We next present the definition of an open set for a general metric space. This also includes the definition of an open set in Euclidean spaces since they are metric spaces.

 

Definition 1.4: Open set (Metric space)

Let $(M, d)$ be a metric space. A subset $A \subseteq M$ is said to be an open set if it contains an open ball around each of its points.

or equivalently,

An open set is a subset of $M$ that can be realized as a union of open balls in $M$.

Figure 2. An open set in $\mathbb{R}^2$. An open ball itself is an open set.

Figure 2 visualizes an open set in $\mathbb{R}^2$. Note that an open ball itself is an open set according to the above definition. Also recall that an open neighborhood of a point is defined as an open set containing the point. Hence, whenever we refer to an open neighborhood of some point $x_0$, it is sufficient to visualize an open ball around $x_0$ with an arbitrarily small radius.

Reader is encouraged verify that following Definition 1.4, open sets of a metric space are closed under union and finite intersection and therefore satisfy axioms in Definition 1.1. Therefore, a metric space (and hence the $n$-dimensional Euclidean space) together with the collection of open sets defined as in Definition 1.4 is a topological space. In the Euclidean case this topology is referred as the Euclidean topology and in the more general case of a metric space it is referred to as the metric topology.

Continuity

We will now discuss the topological definition of continuity of a function, perhaps the most important concept defined on topological spaces. We start from the usual \(\varepsilon\)-\(\delta\) definition of continuity of a function at a point in $\mathbb{R}^n$. The intuition is, a function $f$ is continuous at $x_0$ if it is possible to make \(f(x)\) arbitrarily close to \(f(x_0)\) by choosing \(x\) values sufficiently close to \(x_0\). It is formalized as follows:

Definition 1.5: Continuity at a point (Euclidean space)

A function $f: \mathbb{R}^n \to \mathbb{R}^m$ is said to be continuous at \(x_0 \in \mathbb{R}^n\) if \(\forall \varepsilon > 0, \exists \delta > 0\) such that, \(\|x - x_0 \| < \delta \Rightarrow \|f(x) - f(x_0)\| < \varepsilon \).

Following Definition 1.2, this is equivalent to stating that it is possible to confine $f(x)$ to an arbitrarily small open ball around $f(x_0)$ by confining $x_0$ to a sufficiently small open ball around $x_0$.

Definition 1.5 could easily be generalized to a metric space by replacing difference vector norms with the distance metric. Further, we can convert this definition to an equivalent involving open neighborhoods, using the definition of an open neighborhood in Euclidean spaces.

Figure 2: Defining continuity using the notion of open neighborhoods.

Definition 1.6: Continuity at a point (Euclidean space)

A function \(f: \mathbb{R}^n \to \mathbb{R}^m\) is said to be continuous at \(x_0 \in \mathbb{R}^n\) if for any open neighborhood \(V\) of \(f(x_0)\), \(\exists\) an open neighborhood \(U\) of \(x_0\), such that, \(f(U) \subset V\).

Or equivalently,

Definition 1.7: Continuity at a point (Euclidean space)

A function \(f: \mathbb{R}^n \to \mathbb{R}^m\) is said to be continuous at \(x_0 \in R^n\) if for any open neighborhood \(V\) of \(f(x_0)\), \(f^{-1}(V)\) is an open neighborhood of \(x_0\), where the inverse(or pre-image) of \(f\) is defined as \( f^{-1}(V) = \{x \in X \mid f(x) \in V\}\) for \(V \in R^m\).

This definition does not use distances but the concept of open neighborhoods. Therefore, one could generalize this definition directly to topological spaces. However, continuity at a point is not a very useful concept for topological spaces. Hence, we present the topological definition of a continuous function. In the Euclidean (or a metric) space, a continuous function is defined as a function which is continuous at all points of its domain.

Definition 1.8: Continuous function (Topological space)

A function \(f:X \to Y\) between two topological spaces \(X, Y\) is said to be continuous if for every open set \(V \in Y\), \(f^{-1}(V)\) is open in \(X\). 

In the next article of the series we shall continue our discussion towards understanding topological manifolds, differentiable manifolds and Riemannian manifolds.

References

[1] John M. Lee. Introduction to Topological Manifolds. Graduate Texts in Mathematics. Springer, 2011.
[2] P.A. Absil, R. Mahony, and R. Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2008.     

How to install OpenCV on Mac OS X Lion to work with XCode

I have listed some easy and straight-forward steps below to get OpenCV library working with XCode on Mac OS X Lion without installing unnecessary bulky software on your Mac.

1. Installing CMake

i. CMake is essential to build OpenCV on UNIX. Get CMake Mac OS X binary (dmg) from http://www.cmake.org/cmake/resources/software.html. This comes with a GUI installer, making the installation process easy.

ii. At the end of the CMake installation it will ask whether or not to put CMake into /usr/bin and into PATH environment variable, select Yes and finish the installation. 

iii. Open the Terminal (Launch Pad -> Utilities -> Terminal) and make sure that CMake is successfully installed by entering the following command. It should output the CMake version you have installed.

cmake -version

2. Installing OpenCV

i. Download the latest version of OpenCV for UNIX. At the time of writing this is version 2.3.1 and can be downloaded from http://sourceforge.net/projects/opencvlibrary/files/opencv-unix/2.3.1/ 

ii. Open the Terminal and change directory to the place where you downloaded the OpenCV distribution tarball. e.g. cd ~/Downloads

iii. Execute the following commands one by one. Each command should complete without errors.

tar xvf OpenCV-2.3.1a.tar.bz2 

cd OpenCV-2.3.1 

mkdir build 

cd build 

cmake -G "Unix Makefiles" .. 

make 

sudo make install 

iv. Above commands will build OpenCV into your /usr/local/ directory. 


3. Testing a Sample Program with XCode

i.) Create a new Command Line Tool with a name of your choice. Set the type as C++ (See the screenshot below).

 ii.) After the new project is opened in XCode, click on the project name. Click Build Settings > All.

iii.) Search for 'Header Search Paths', set the value of Header Search Paths to /usr/local/include

 

iv.) Right click on the project name and select Add File To....

 

v.) A new file selector window will open. Press '/' key to open Go to folder box. Type /usr/local/lib there and hit Return.

vi.) Select the following files from /usr/local/lib and add them to your project. 

libopencv_core.2.3.1.dylib
libopencv_highgui.2.3.1.dylib

v.) Open main.cpp and put the following code there. This code simply reads an image and displays it in a new window. Make sure you put the actual path of your image in the code.

#include <iostream>
#include <opencv2/opencv.hpp>

using namespace std;
using namespace cv;

int main (int argc, const char * argv[])
{
    Mat img = imread("/Users/sadeep/Desktop/image.jpg"); //Change the image path here.
    if (img.data == 0) {
        cerr << "Image not found!" << endl;
        return -1;
    }
    namedWindow("image", CV_WINDOW_AUTOSIZE);
    imshow("image", img);
    waitKey();
}

vi.) Click Product -> Build. This should show the "Build Successful" message.

vii.) Click Product -> Run. Your image will open in a new window which will close upon a key press.

Happy coding with OpenCV!