# Introduction to Reproducing Kernel Hilbert Spaces

#### Author: [Sharath Chandra](https://sharathraparthy.github.io/)

###### tags: vector-spaces, metric-spaces, cauchy-sequences, banach-spaces, hilbert-spaces, reproducing-kernel-hilbert-spaces
# Aim:
To understand what are Reproducing Kernel Hilbert Spaces. But before that it's very important to skim through the fundamentals of linear algebra. So, in subsequent sections I will be discuss about the following:
* Vector Spaces
* Vector Normed Spaces
* Metric Space
* Cauchy Sequence
* Completeness of a sequence
* Banach Spaces
* Inner Product Spaces
* Hilbert Spaces

I know that this looks scary at first glance but I feel that these are important to understand the concept of RKHS. All the definition's are ordered in a way that the current definition demands the understanding of the previous one.

## Vector Spaces:
**Definition**: A vector space over a field $F$ is a set $V$ which follows the following properties:
1. Vector addition: Two vectors $u$ and $v$ can be addded to give a third vector $w$ which belongs to same set.
2. Scalar multiplication: $F \times V \rightarrow V$, any scalar $a$ can be multiplied with a vector $v$ to give a vector which belongs to same set.

## Normed Vector Spaces:
**Definition**: Intuitively we can define a normed vector space as a vector space where the lengths on the vectors are defined. More mathematically, a vector space is said to be "Normed Vector Space" if it satisfies the following axioms.
1. $\lVert v \rVert \geqslant 0$
2. $\lVert v \rVert = 0$ if and only if $v = 0$
3. $\lVert \alpha v \rVert = |\alpha|\lVert v \rVert$ for any scalar $\alpha$
4. For any $u, v \in V$, $\lVert u + v \rVert \leqslant \lVert u \rVert + \lVert v \rVert$

## Metric Space
A metric space $(M, d)$ is a set $(M)$ with distance measure$(d)$ between it's elements. We can call a space a metric space if it obeys the following axioms. For all $x, y, z \in M$
1. $d(x, y) \geqslant 0$
2. $d(x, y) = 0$ if and only if $x = y$
3. $d(x, y) = d(y, x)$
4. $d(x, z) \leqslant d(x, y) + d(y, z)$

## Cauchy Sequence:
A cauchy sequence is a sequence of elements from a set where the nearby elements in the set gets increasingly closer to each other.This can be seen the figure below.

And usually all the cauchy sequences are defined on the metric spaces (because from the definition it is a set with a distance measure). We say that a cauchy sequence (or infact any sequence) is convergent if it has a limit as $n \rightarrow \infty$ and that limiting value should be from the same set on which the sequence is defined.

There are some cases where the limit exists but doesn't belong to the same space. In that case the cauchy sequence is not conergent. Ex: Let us define a sequence on rational numbers $Q$ and assume that the sequence has a limit and it converges to $\sqrt 2$. Since $\sqrt 2$ is an irrational number we can't say that the sequence is convergent even though it has a limit.

Now that we understood what exactly is cauchy sequence and when it is convergent, let's learn about the completeness.

## Completeness:
A metric space $(M, d)$ is said to be complete if every cauchy sequence defined on it is convergent. This is very important definition because whatever we are going to discuss from now on depends on this.

## Banach Spaces:
A banach space is a normed vector space where all the cauchy sequences converge. Intuitively, it is a vector space, where norms are defined, which is *complete*

In linear algebra we often come across the term *Inner Product Spaces* What exactly are they in mathematical sense? We often calculate the the inner product of vectors in machine learning so, it's very important to get a sense of what it is.

## Inner Product Space:
In laymen terms, when we multiply a vector with another vector in such a way that the result is a scalar quantity, then this type of multiplication is called inner product and a space in which the inner products are defined is called an inner product space.

Mathematically, an inner product space is a vector space $V$ over a field $F$ with a binary operator, $<., .>: V \times V \rightarrow F$. It obeys the following axioms. For all $x, y \in V$ and $a \in F$
1. Conjugate Symmetry : $<x, y> = \bar{<y, x>}$
2. Linearity : $<ax, y> = a<x, y>$
3. Positive definiteness : $<x, x>$ $\geqslant 0$

We can see that the inner product spaces has a norm induced by it which is called $l_2$ norm or the euclidean norm.
And lastly, let's learn about the hilbert spaces which is the foundation for RKHS.

## Hilbert Spaces
So, the hilbert spaces are nothing but the banach spaces where the norm is induced by the inner product. Or in other words, we can say that the Hilbert space is a normed vector space, where the norm is due to the inner product, which is complete. This definition is very important for our further discussion on RKHS.

## Kernels
Kernel is a way of calculating the dot product of two vectors in a high dimesional feature space. Let's say we have a function $\phi : \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$ which maps from $\mathbb{R}^{n}$ to some high dimensional feature space $\mathbb{R}^{m}$, then the dot product between two vectors $x$ and $y$ is $\phi(x)^{T}\phi(y)$ is called a kernel function $k(x, y)$. From the definition we can say that the kernels are bivariate functions.

## Reproducing Kernels
A kernel defined on the hilbert space $H$ is said to be reproducing kernel if it follows the following properties.
1) For every $x_0 \in X$, $k(y, x_0)$ is a univariate function in $H$. This means that if we fix x (or y), the resulting function, which is univariate, must belong to the same Hilbert space $H$.
2) Reproducing Property : For all $x_0 \in X$ and $f \in H$, $<f(.), k(., x_0)> = f(x_0)$. As we know if a function belongs to a hilbert space then we can calculate an inner product. Since from (1), $k(x_0, y)$ is a function in $H$ we can easily calculate the inner product. The reproducing property suggests that the resultant value of the inner product must be equal to $f(x_0)$.

## Point Evaluation Functions
We have seen that every element in a hilbert space is a function from $X \rightarrow \mathbb{C}$ and a conventional set in $H$ is also a function which maps from $H \rightarrow \mathbb{C}$. Lets call these as functionals (functions of functions). So, a Point Evaluation Functional $L_x : H \rightarrow \mathbb{C}$ defined at a point $x \in X$ is $L_x := f(x)$.

## Reproducing Kernel Hilbert Spaces
A hilbert space $H$ of complex valued functions on a non-empty set $X$ is called **Reproducing Kernel Hilbert Space** if the point evaluation functional is a bounded linear operator.