Welcome to Reproducing Kernel Hilbert Space

In a series of posts I hope to introduce Mathemafrica readers to some useful data analysis methods which rely on operations in a little back-water of Hilbert space, namely Reproducing Kernel Hilbert Space (or RKHS).

We’ll start with the “classic” example. Consider the data plotted in figure 1. Each data point has 3 “properties”: an $x_1$ coordinate, an $x_2$ coordinate and a colour (red or blue). Suppose we want to be able to separate all data points into two groups: red points and blue points. Furthermore, we want to be able to do this linearly, i.e. we want to be able to draw a line (or plane or hyperplane) such that all points on one side are blue, all points on the other are red. This is called linear classification.

Figure 1: A scatter of data with three properties: an x_1 coordinate, an x_2 coordinate and a colour.

Suppose for each data point we generate a representation of the data point $\phi(x)=[x_1, x_2, x_1x_2]$.…

Chain Rule.

Definition:

The chain rule is a method for differentiating a function of a function, or differentiating composite functions.

Consider the expression $y = sin(x^2)$. We notice that this is not a normal sine function. It has an $x^2$ as argument for the sine function. Therefore, we can consider the $x^2$ in the sine function as a whole different function. This can be broken into two functions, $f(x)$ and $g(x)$.

If we consider $f(x) = sin(x); g(x) = x^2$, we can write $y = f(g(x))$.

In order to differentiate a composite function, $y = f(g(x))$, i.e; to find $y'$, we let

$u = g(x)$  and  $y = f(u)$

What this implies is that whatever $g(x)$ is, u will be equal to that. Then, the process of differentiating is to find

• $\frac{du}{dx}$ (as u will be a function of x).
• $\frac{dy}{du}$

Finally, we can write,

$\frac{dy}{dx} = \frac{dy}{du} \cdot \frac{du}{dx}$

Back to our example, $y = sin(x^2)$; remember that $f(x) = sin(x)$ and $g(x) = x^2$. We let

$u = x^2$  and  $y = f(u) = sin(u)$

Therefore,  $\frac{du}{dx} = 2x$ and  $\frac{dy}{du} = cos(u)$

This leaves us with  $\frac{dy}{dx} = cos(u) \cdot 2x$. We can simplify the equation by writing

$\frac{dy}{dx} = 2xcos(x^2)$

Note that the u in the cosine function is replaced with $x^2$.…

IMU Breakout Graduate Fellowships – Call for Nominations by professional mathematicians nominating highly motivated and mathematically talented students from developing countries

A very interesting opportunity for talented potential graduate students. This is taken directly from the Commission for Developing Countries website.

Please think about finding a potential supervisor if you think that you qualify, such that they can nominate you.

Thanks to a generous donation by the winners of the Breakthrough Prizes in Mathematics – Ian Agol, Simon Donaldson, Maxim Kontsevich, Jacob Lurie, Terence Tao and Richard Taylor– the International Mathematical Union, with the assistance of FIMU and TWAS is launching a fellowship program to support postgraduate studies, in a developing country, leading to a PhD degree in the mathematical sciences. The IMU Breakout Graduate Fellowships offer a limited number of grants for excellent students from developing countries.

Professional mathematicians are invited to nominate highly motivated and mathematically talented students from developing countries who plan to complete a doctoral degree in a developing country, including their own home country.…

IMU Breakout Graduate Fellowship Program – Apply now!

The IMU (International Mathematical Union) has recently launched the novel IMU Breakout Graduate Fellowship Program.

Thanks to a generous donation by the winners of the Breakthrough Prizes in Mathematics – Ian Agol, Simon Donaldson, Maxim Kontsevich, Jacob Lurie, Terence Tao and Richard Taylor – IMU with the assistance of FIMU (Friends of the IMU) and TWAS (The World Academy of Sciences) has launched a fellowship program to support postgraduate studies in a developing country, leading to a PhD degree in the mathematical sciences. The IMU Breakout Graduate Fellowships will offer a limited number of grants for excellent students from developing countries. The program will be administered by CDC (Commission for Developing Countries), a commission of IMU.

Professional mathematicians are invited to nominate highly motivated and mathematically talented students from developing countries who plan to complete a doctoral degree in a developing country, including their own home country. Nominees must have a consistently good academic record from the high school level and must be seriously interested in pursuing a career of research and teaching in mathematics.

Proof by induction winner: Gianluca Truda

With many congratulations for the winning entry, as voted for by mostly MAM1000W students!

At the end of every year, many families celebrate the holiday season by decorating a Christmas tree, and almost all of them will use some form of lights. The kind of cheap lights that sit on a long wire that gets wrapped around a tree, and then sparkle in a whole lot of awesome colours when you plug them into the power socket.

In my family, we have a whole lot of these kinds of cheap, fragile lights in a big box. Every year, when we decorate the tree, the box gets opened and is full of hopelessly tangled wires which were hastily shoved in the year before. It’s always a bit of a pain untangling the wires and it can get really
boring testing each string of lights to see if they are still working.…

Logical implications and the structure of if and only if statements

We had a homework assignment a couple of weeks back. It was looking at mathematics in a very different way from how many had seen it before, and it caused a lot of confusion. I would like to try and add some clarity to what we were doing. My thought was, rather than going through the questions themselves, I would like to add annotations to the proof itself. Let’s see how this works. The proof that you were given is in black, the annotations are in blue, and after I’ve been through the proof, I will expand on it in a simplified form.

Theorem: The function f is differentiable at x=a if and only if there is a constant m and a function E of x, defined for all $x \not = a$, such that

$f(x)=f(a)+m(x-a)+E(x)(x-a)$ for all $x \not = a$      – (eq 1)

and,

$\lim\limits_{x\to a}E(x)=0$.

(If both these conditions are satisfied, then $f'(a)=m$.)

What we are doing here is giving another definition of differentiability (at a particular point, a).

Computational Complexity: Article 4

Equations Speak Louder Than Words

We have thus far created a strong link between familiar intuition and formal mathematics, with the intent of constructing a framework with which to better analyse and understand the complexity of computations. We continue on this trajectory by classifying decision problems according to the resources they consume on deterministic (for the same input, will always produce the same output on different runs) and non-deterministic (for the same input, can produce different outputs on different runs) Turing machines. Our resource of consideration will be time, T(n), called time complexity, where n is input length. A similar analysis can be done for space or memory.

Definition 4.1 Let T(n): N → N (T(n)‘s domain and codomain is the set of Naturals) be a proper time function. Then DTIME(T(n)) is the time complexity class containing languages that can be recognized by deterministic Turing machines (DTM’s) that halt on all inputs in time T(n), where n is the length of an input.…

Proof by induction for a non-mathematician – a competition: Vote for the winner!

I set a voluntary assignment for my course a few weeks back. Students had just learned about proof by induction, and I tend to find that this is a subject which many get confused by. I think that one of the best ways to really understand a topic is to try and teach it to someone else, so I set up an exercise which was to write an explanation of Proof by Induction for a young high school student. We had around 100 entries, which took a while to read through! Of these 100 entries there were four which stood out (and many which were also very good). We (myself, and two senior tutors) have been unable to come up with an outright winner. That’s where you come in!

Please take a look at the following entries, and vote for the one that you think is best at this link: https://www.surveymonkey.com/r/9K3P8BJ.…

The squeeze (or sandwich) theorem

Let’s say I ask you how tall Craig is going to be when he’s 15 years old, and let’s say, given his genetic information, you just can’t tell what height he will be at that age. However, you do know that he’s going to be taller than Lisa, and shorter than Khangelani up until the age of 15 (they are all the same age). With this information alone, you haven’t learnt much about the height of Craig when he’s 15. However, what if you can figure out, using your clever genetic detective work, that at the age of 15 Lisa and Khangelani will be the same height? The only way for this to be true, is if Craig (whose height is sandwiched in between that of Lisa and Khangelani) is also the same height at that age.

That’s really all the sandwich theorem is. Let’s look at a mathematical example.…

Greetings from Bibliotheca Alexandrina

 I just received the info below on Bibliotheca Alexandrina and its new African Networks and I thought it makes sense to share it on mathemafrica. I really like the idea of historical places connecting to new technologies. Here is a link to a film (in French) about the historical library at Alexandria:   Greetings from the Bibliotheca Alexandrina (BA) in Egypt. We are pleased to announce the launch of “BA African Networks”. Below you will find a description of the networks. You are most welcome to explore our portal and our five networks through the following link. http://afn.bibalex.org/GeneralPortal.aspx The Bibliotheca Alexandrina (BA) follows in the footsteps of the Ancient Library of Alexandria as a meeting point for cultures and civilizations. It aims to rise to the digital challenge in order to develop African innovation through the use of science and technology in networks that extend throughout Africa. The new goal set by the BA is to connect those with common interests and expertise to hasten the development of knowledge and enable immediate sharing of knowledge and contributions.