Fourier Transform Clarified

This article should allow you to understand Fourier transform much better. It should clarify basic principles and several important details, which are not said in other articles. It is a little informal, but all formalities should be obvious after reading it.

Prerequisities

Before you start to read, you must know, what is complex number, trigonometric functions (sine, cosine) and integral.

Introduction

I assume, that you have already heard about Fourier transform. It is usually shown, how the sum of sinusoids having different period creates "square" or some other function. Then cosines come out, complex numbers and deadly expression $e^i$ (you know, that $e^3 = e \cdot e \cdot e$, but what the hell is $e^i$?). In this article, we will look at things differently.

Imagine a wheel, which has a radius $r_0$, it has a red dot on the right side from center, it has an initial angle $\alpha_0$ and rotates with speed (angular velocity) $s_0$. This red dot draws an image of a circle.

Imagine, that at the red dot of that wheel, there is another wheel with a radius $r_1$, angle $\alpha_1$, that rotates with a speed $s_1$. This system of two wheels draws more interesting curve.

Imagine, that there may be another wheel at the dot of the last wheel, and another wheel on top of that wheel ... There may be infinitely many wheels. Which curves can be drawn by such systems of wheels?

Theorem: We can draw any curve using a system of wheels.

We can draw not only a circle, but also a square, triangle or a line. Here is a system of wheels, which draws Homer Simpson. We can notice, that each wheell just "adds a shift" to previous wheel. So we can interchange wheels with each other, the order of wheels is not important (because addition is commutative).

Theorem: If two wheels have the same speed, they can be "merged" into a single wheel (with the same speed, but different radius and angle).

Let's talk about different problem. We have a curve (continuous function $f: \mathbb{R} \rightarrow \mathbb{R}^2$), that for each parameter $t$ returns a position (x,y) - point of curve. We want to find a system of wheels, which draws that curve. System of wheels can be represented also as a function $g$, for each speed $s$ it returns a pair (r,$\alpha$) - radius and initial angle of a wheel with speed $s$ in that system (e.g. when we don't need some wheel, $g$ gives it a radius 0). Take a deep breath and get ready for the most shocking discovery of your life. Operation, that finds a wheel system $g$ for a curve $f$, is called Fourier transform.

Examples

Let's have a curve, that has a single point (0,0), i.e. $f(t) = (0,0)$. What is the Fourierova transform of it? We simply set all radii and angles to 0, i.e. $g(s) = (0,0)$.

Let's have a curve, a circle, that has a radius 0.6 and center at the point (4,3), i.e. $f(t) = (4+0.6\cdot \cos(t), 3+0.6\cdot \sin(t))$. What is the Fourier transform of taht curve? We can shift the whole curve using wheel with a speed 0, we can draw a circle using some other wheel. For example:

  • $g(0) = (5, 37.64°)$
  • $g(1) = (0.6, 0)$
  • $g(s) = (0,0)$ otherwise

Complex numbers

We already know, what Fourier transform is. It looks for a function "related" to some other function. The input function works with coordinates x and y, whilst the output function works with radii and angles. It would be great to "unify" them. Moreover, the system of wheels is not unique for a curve, e.g. if we add 360° to initial angle of some wheel, it would still draw the same curve.

Instead of 2D coordinates for curve, let's work with complex numbers. So instead of $(x,y)$ let's have $(x+y\cdot i)$. Our curve is $f: \mathbb{R} \rightarrow \mathbb{C}$. That was quite easy. The second part will be slightly more complicated.

We have wheels at the output (pairs radius + angle). We would like to use complex numbers here too. Let that number be the initial position of red dot in a complex plane (due to the center of wheel). So, instead of $(r,\alpha)$ we have a complex number $r \cdot (\cos(\alpha)+\sin(\alpha)\cdot i) = (a + b\cdot i)$. But how do we rotate such number e.g. by 30 degrees? In our first representation, we just added a rotation to previous angle and received a new angle (radius remained the same). But how to rotate a complex number? Read carefully! To rotate a complex number, one just multiplies it by another complex number. Namely, $(\cos(30°) + \sin(30°)\cdot i)$. Our system of wheels also has a form $g: \mathbb{R} \rightarrow \mathbb{C}$. now

What is the advantage of using complex numbers instead of classic $\mathbb{R}^2$ and wheel systems? It makes everything more complicated. Complex numbers are hard to multiply and nobody likes them. It is not that easy to see wheels behind the complex numbers, but wheels are still there! We actually have few benefits. Two things (curves and wheel systems) have the form of $\mathbb{R} \rightarrow \mathbb{C}$. Also, Fourier thransform between them is unique - there is only one set of wheels for a curve (when both represented by complex numbers). It can be shown, that FT is injective and surjective. So there should be an inverse FT, that finds a curve for a system of wheels.

Let's define FT once again. It is still an operation, that finds a set of wheels for parametric curve, but both things are represented by complex numbers (using functions $\mathbb{R} \rightarrow \mathbb{C}$).

Let's clarify, how wheel system works, so it is clear what FT does. A red dot of the whole system should draw our curve, so for parameter $t$ red dot should be at the position $f(t)$. For $t=0$ each wheel should be at its initial position. When $t$ is increased by 1, the wheel with a speed 1 should rotate once (by $2 \pi$) and generally, a wheel with speed $s$ should rotate "$s$ times" (by $s \cdot 2 \pi$).

Properties of Fourier transform

Let's say, we have a parametric curve $f$ and we have found a wheel system $g$ for it. Now we "zoom in" the curve with parameter $k$, $f_2(t) = k\cdot (x + y\cdot i)$. How would the system of wheels look like for this new curve? We just multiply a radius of each wheel by $k$! In our representation, we multiply complex numbers. So:

$FT(f)=g \Rightarrow FT(f_2) = k \cdot g$.

A little shocking detail: it works even for $k\in \mathbb{C}$ (as you can see from Moivre's formula).

Now we have curves $f_1, f_2$. Let's create a new curve by "adding" them together, so $f_3(t) = (x_1+y_1\cdot i) + (x_2+y_2\cdot i)$. Each curve has its own system of wheels $g_1, g_2$. How does the system looks like for $f_3$? We just connect one set to the red dot of another set. We would have two wheels for each speed, and, as mentioned above, we can merge them into one wheel. How exactly does it look like? We just add complex numbers! so:

$FT(f_1)=g_1, FT(f_2)=g_2 \Rightarrow FT(f_3) = g_1 + g_2$.

These properties are often called Linearity of Fourier transform.

Computing the Fourier transform

Computing inverse FT

We want to know, how to transform between curves and wheel systems. First, let's talk about inverse FT, because it is easier. We know a set of wheels $g(s)$ and we are interested in a motion of red dot - its position at parameter $t$, i.e. $f(t)$.

Let the system have just one wheel with non-zero radius. It has a speed $s$, radius and initial angle are represented by a complex number $g(s) = a+b\cdot i$. Where is the point of curve at $t$? We just rotate the wheel to an angle $t*s$ and compute the position of red dot. We already know how to rotate complex numbers.

$ f(t) = (\cos(t\cdot s\cdot 2 \pi) + \sin(t\cdot s\cdot 2 \pi) i) \cdot g(s) $

What if we have $n$ wheels (with non-zero radii)? Each wheel has its speed $s_j$ and complex number representing radius and angle. Each wheel determines a shift from a red dot of previous wheel, so we just add these shifts.

$ f(t) = \sum\limits_{j=1}^n (\cos(t \cdot s_j \cdot 2 \pi) + \sin(t \cdot s_j\cdot 2 \pi) i) \cdot g(s_j) $

What if we have infinitely many wheels? The sum becomes an integral.

$ f(t) = \int\limits_{s\in\mathbb{R}} (\cos(t\cdot s\cdot 2 \pi) + \sin(t \cdot s \cdot 2 \pi) i) \cdot g(s) \mathrm{d} s$

Since we know, how wheels work and how to rotate complex numbers, we don't have to remember this equation. We can "invent" it when we need it.

Computing FT

FT is more complicated. We have a curve $f$ a we want to find a system of wheels $g$. We want to know a complex number (radius + angle) for a wheel with a speed $s$. Here is an equation:

$g(s) = \int\limits_{t\in\mathbb{R}} (\cos(- t\cdot s\cdot 2 \pi) + \sin(- t \cdot s \cdot 2 \pi) i) \cdot f(t) \mathrm{d} t$

I don't fully understand an idea behind that equation. You may notice, that when $s=0$, the value inside brackets is 1 and the result is an "integral over the whole curve" (= "average point"), which then corresponds to shift of the whole curve away from center.

When $s$ is not zero, expression inside brackets generates a circular motion, but in different direction, than IFT. The result may mean an average point, multiplied by circular motion.

Fourier series

Theorem: When a curve $f$ is periodic, it can be expressed by system of wheels with integer speeds.

We noticed it in circle, where we needed just one wheel with a speed 1. We will need much more wheels to draw a square, but thanks to the theorem we know, that we will only need wheels having speeds 0, 1, 2, 3, ... The FT for periodic curve $f$ is system of wheels $g$ in form $\mathbb{N}\rightarrow\mathbb{C}$. Inverse FT does not have to be integral, but just infinite sum (series):

$ f(t) = \sum\limits_{j\in\mathbb{N}} (\cos(t \cdot j \cdot 2 \pi) + \sin(t \cdot j\cdot 2 \pi) i) \cdot g(j) $

Complex exponential

As we have shown in an article about Taylor polynomial, function $e^x, x \in \mathbb{R}$ has Taylor polynomial:

$e^x = \frac{x^0 }{ 0! } + \frac{x^1 }{ 1! } + \frac{x^2 }{ 2! }+ \frac{x^3 }{ 3! } + ...$

Inspired by that, let's define a complex exponentiation:

$e^{a+bi} = \frac{ (a+bi)^0 }{ 0! } + \frac{ (a+bi)^1 }{ 1! } + \frac{(a+bi)^2 }{ 2! }+ \frac{(a+bi)^3 }{ 3! } + ...$

Now let's put $ix$ into exponent:

$e^{ix} = \frac{{(ix)}^0}{0!} + \frac{{(ix)}^1}{1!} + \frac{{(ix)}^2}{2!} + \frac{{(ix)}^3}{3!} + ...$

Let's slightly reorder summands:

$e^{ix} = \left(\frac{{(ix)}^0}{0!} + \frac{{(ix)}^2}{2!} + ...\right) + \left(\frac{{(ix)}^1}{1!} + \frac{{(ix)}^3}{3!} + ...\right)$

Let's get i in front of bracket:

$e^{ix} = \left(\frac{{(ix)}^0}{0!} + \frac{{(ix)}^2}{2!} + ... \right) + i\left(\frac{x^1}{1!} + \frac{i^2x^3}{3!} + ...\right)$

$i$ is always powered to even power, so it will just multiply the number by 1 or -1:

$e^{ix} = \left(\frac{x^0}{0!} - \frac{x^2}{2!} + ... \right) + i\left(\frac{x^1}{1!} - \frac{x^3}{3!} + ...\right)$

From the previous article we know, that the first bracket is Taylor series for cosine, second bracket for sine (also called Euler's formula):

$e^{ix} = \cos(x) + i \sin(x)$

Now we can write $e^{ix}$ everywhere instead of sines and cosines, e.g. for FT:

$g(s) = \int\limits_{t\in\mathbb{R}} (\cos(- t\cdot s\cdot 2 \pi) + \sin(- t \cdot s \cdot 2 \pi) i) \cdot f(t) \mathrm{d} t = \int\limits_{t\in\mathbb{R}} e^{-t\cdot s \cdot 2 \pi \cdot i} \cdot f(t) \mathrm{d} t$

Notice, that it is not possible to understand Euler's formula (or FT written using Euler's formula) without a proper knowledge of differential calculus, integrals and Taylor series.

There are 3 reasons to write FT with $e^{ix}$:

  • to make equations shorter
  • to make person looks smarter
  • to make it even harder for a student to understand FT

Old comments (closed because of spam)

Comments are closed.