Fourier
Complex numbers and Fourier transformation.
Complex Numbers
Complex numbers consist of a real and an imaginary part:
\[z = x + iy\]The real part of $z$ is $Re(z) = x$, and the imaginary part of $z$ is $Im(z) = y$.
Complex numbers are sitting in the $x-y$ plane $\R^2$ where $x$ the real part gives you the $x$ coordinate and $y$ the imaginary part gives you the y coordinate.
Now, if you think of complex numbers in this way, then vector addition is defined in the same way as if you were working in $\R^2$ with vectors $(x, y)$.
Complex numbers have the same vector addition and scalar multiplication as vectors in $\mathbb{R}^2$:
Addition
\[(a + ib) + (c + id) = (a+c) + i(b+d)\]Multiplication
\[i^2 = -1, i = \sqrt{-1}\] \[\begin{align*} (a + ib)(c + id) &= a(c+id) + ib(c+id) \\& = (ac+aid) + (ibc + i^2bd) \\&= ac - bd + i(ad + bc) \end{align*}\]Complex conjugate
\[(a+ib)^* = a - ib\]Length squared
\[(a + ib)^*(a + ib) = (a - ib)(a+ib) = a^2 + b^2\]Division
\[\begin{align*}\frac{a + ib}{c + id} & = \frac{(a+ib)(c + id)^*}{(c+id)(c+id)^*} \\&= \frac{(a+ib)(c-id)}{c^2 + d^2} \\&= \frac{ac + bd + i(cb - ad)}{c^2 + d^2}\end{align*}\]Alternative Form
We like to work with two different representations of complex numbers.
The first one is the one we just discussed where you think of your complex numbers as a two-dimensional vector for the x coordinate is the real part and the y coordinate is the imaginary part.
However, you can also think of complex numbers as being described by the arrow that points from the origin to the point that represents the complex number => Polar coordinates.
This arrow has a length $r$, and the angle $\theta$. These two numbers, the length and the angle with the x-axis describe a complex number uniquely. We often write this on an exponential form $z = re^{i\theta} = r(\cos \theta, \sin\theta)$.
Euler’s formula
We have the two equivalent representations $z = x + iy = re^{i\theta}$, where $x$ and $y$ are the coordinates of $z$. By the definition of the cosine, we have
\[x = r\cos \theta,\]and by the definition of the sine, we have
\[y = r\sin \theta.\]In particular, $r = 1$ gives rise to Euler’s formula
\[e^{i\theta} = \cos \theta + i \sin \theta\]Multiplication of complex numbers
Multiplication of complex numbers is easy in polar coordinates: $r_1e^{i\theta_1} \cdot r_2e^{i\theta_2}$
\[\begin{align*} r_1e^{i\theta_1} \cdot r_2e^{i\theta_2} & = r_1r_2e^{i\theta_1}e^{i\theta_2} \\ & = r_1r_2(\cos\theta_1 + i\sin\theta_1)(\cos\theta_2 + i\sin\theta_2) \\ & = r_1r_2(\cos\theta_1\cos\theta_2 - \sin\theta_1\sin\theta_2 + i(\sin\theta_1\cos\theta_2 + \cos\theta_1\sin\theta_2)) \\ & = r_1r_2(\cos(\theta_1 +\theta_2) + i\sin(\theta_1 + \theta_2)) \\ & = r_1r_2 e^{i(\theta_1 + \theta_2)} \end{align*}\]In the last step, use the Euler formula to go back to the polar coordinate form.
In other words, the usual exponential algebra holds also for complex numbers.
Moreover, we get a geometric interpretation of the multiplication of complex numbers.
Fourier Transform and series
Basis
This is the mathematical trick if you want to express the basis for our signal transform.
You need to notice that
-
through the exponential complex, the cosine and sine come in pairs and they have the same frequency.
-
frequency is the inverse of the wavelength.
It has a face that is a measure of how far it’s been shifted from its origin.
But by the combination of this cosine and sine, we are explicitly modeling the frequency with $2\pi ux$ but implicitly modeling the face by how much is there of this cosine versus how much is there if this sine is in a particular signal. => Don’t show it here.
-
I like to think of the frequency is by multiplying by $2\pi$, some others prefer to combine $2\pi u$ into $w$. This is just a scaling. It doesn’t matter but when we start to integrate, scaling matters they become constants in front of the integration as we’ve seen.
Transform
The key concept of a transform is that you can take a signal or an image and change it into one thing, or one thing and then change it back.
This is different than for example, projection. What you do with your camera when you take a picture of the room captures some information in the room, but you cannot reconstruct the room from your picture. You are shattering the person behind. So I only have partial information when I take a projected image.
A transformation is different, you can go back and you can go forward. You don't lose any information.
-
In the continuous version (the transformation is this integral in the part of Transform), I take a function $f(x)$ and I multiplied by this cosine sine pair or the complex exponential. And up here, they are both $x$ and $u$.
So it’s a complex exponential both in the original domain and the resulting domain. But we only integrate the $x$ away. This integral removes $x$, that’s the reason why only $u$ left here.
-
The first one is typically called forward, while the second one is called backward. => Question of Perspective. Normally, we think of standing in the special $x$ domain going into the frequency domain $u$. But these are just names. You should notice that there’s a minus in the forward direction and a plus in the other.
You should also keep in mind that this is integral and not every function is integrable. So we are only talking about a subset of functions that have a Fourier transformation.
Series
The series are discrete versions of these transforms. Those are the ones that are with some signs down here.
\[\begin{align*} F(u) & =\frac{1}{N} \sum^{N-1}_{x = 0} f(x)e^{-i2\pi ux/N} \\ f(x) & =\frac{1}{N} \sum^{N-1}_{u = 0}F(u)e^{i2\pi xu/N} \end{align*}\]All the discrete signals have Fourier series. All the ones that we get on a computer can be Fourier transformed.
However, if you’re modeling it as a continuous function, it might not be shown. I think most you will work with will have Fourier transform.
You should notice that it’s implied that $f(x)$ is a discrete sample signal, and there are $n$ points to it. For now, just imagine this as $N$ points that you’ve sampled, temperature, and the like. And what you can get out of it are $N$ values in the Fourier transform domain.
Then, we take the basis function and this becomes a matrix that you can multiply with your sample function $f(x)$. And as such all that’s going on here is a base change and it turns out that this base is invertible.
So that is the language of Fourier transformation.
Power spectrum, length, angle
There are some key derived functions that we use all the time.
Power / Power spectrum
We take the power spectrum is that we take the Fourier transform on each individual complex number. For every value $u$ coming out of this and we calculate the length squared. For example, by multiplying by the complex conjugator.
\[P(u) = |F(u)|^2\]We also often talk about the length, and an angle => From the perspective of the vector.
\[len(u) = \sqrt{P(u)}, \ angle = \tan^{-1}\frac{Im(F(u))}{Re(F(u))}\]Odd and even functions
Thinking of functions as a combination of even and odd turns out to be extremely useful in this context.
The property of an even function is that,
\[\epsilon(x) = \epsilon(-x)\]If you look at the corresponding negative position, you have the same value.
While for the odd functions, just like the sine. It’s the same value but negative.
\[o(x) = - o(-x)\]Maybe you haven’t thought of this, but all functions can be written as a combination of an odd function and an even function.
Any $f$:
\[f(x) = \epsilon(x) + o(x) \\ \begin{align*} \epsilon (x) &= \frac{1}{2}(f(x) + f(-x)) \\ o(x) & = \frac{1}{2}(f(x) - f(-x)) \end{align*}\]But what about an even function times an odd function?
On the positive side of the axis, we have even one value and odd another value. These two values on the other side of the axis where the even is the same but the odd has a switch sign. So I add these two, I get $0$.
So, if I constantly pair the multiplication of an even and odd function and just add these two together, I always get $0$.
The key thing to realize here is that we are going to look at functions that we will multiply by an even and an odd function. => $\cos(2\pi ux) - i\sin(2\pi ux)$
Basis
\[F = \mathcal{F}(f) \\ f(x) \Join F(u) \\ (f * g)(x) = \int^{\infty}_{-\infty}f(\alpha)g(x - \alpha)d\alpha\]Fourier transform
\[\begin{align*}\mathcal{F}\{\epsilon(x) + o(x) \} &= \int^\infty{-\infty}(\epsilon(x) + o(x))(\cos (2\pi ux) - i\sin(2\pi ux))dx \\ &= \int^\infty{-\infty}\epsilon(x)\cos(2\pi ux)dx - i\int^\infty{-\infty}o(x)\sin(2\pi ux)dx\end{align*}\]Because both $f$ and the alternative way for exponential form one is (even and odd) and they get paired, the result still can be thought of as even and odd.
Consequences
2D Fourier Transform and series
Basis
\[e^{-i 2\pi (ux+vy)} = e^{-i2\pi ux}e^{-i2\pi vy}\]Transform
Linear separable => You can transform on all rows and then do the other one.
Series
Fourier series assumes periodicity
We use this picture to do the Fourier transformation in the computer, and that is the Fourier series assumes the signal is periodic.
The impolication of that is when I do Fourier transformation of my image, the right-most pixel is the left-most pixel. So when you see the image, you should think of it as sort of wrapping around in both $x$ and $y$.
Cosine noise has 2 peaks in the Fourier Domain
In the left picture, I have two dots here and they are running on a circle. That means, I have changed my original image by adding a cosine function to it because when I add these two dots in my fourier domain, that’s the same as adding a cosine function in the real domain.
The right picture shows you some of these waves that the image is built up.
Or, if I have an image where there’s such a high frequency noise on it. It is very easy to remove. Because I fourier my image and set the corresponding frequencies to $0$, then, it goes away. You can’t see that you also remove the frequency from the original image as it is really neat. => Hence, this type of noise is very easy to remove.
Convolution Theorem
$\alpha$ is a new integration variable.
You want an image or a signal and then you have your kernel and you flip the kernel and then you move it around.