Discrete Fourier Transform, intro to

I have been reluctant on writing a post about the discrete Fourier transform (DFT) for a while because I don't feel comfortable with all the details. In fact, a few weeks ago was the first time I saw the DFT in an academic setting. But even then, the introduction given in CS371 was a high-level overview of the theory. So here it goes. Reader discretion is advised.

It can be shown that a "nice" function $f(x)$ (the true meaning of "nice" is beyond the scope of my current knowledge) defined on the interval $x \in [a,b]$ can be approximated by a Fourier series:

$$g(x) = \frac{a_0}{2} + \sum_{k=1}^{\infty}\bigg[a_k\cos(k\frac{2\pi x}{b-a})+b_k\sin(k\frac{2\pi x}{b-a})\bigg]$$

with

$$a_k = \frac{2}{b-a}\int_a^bf(x)\cos(k\frac{2\pi x}{b-a})dx$$

$$b_k = \frac{2}{b-a}\int_a^bf(x)\sin(k\frac{2\pi x}{b-a})dx$$

Just like the Taylor series, this result is quite miraculous if not more. The way I see it is that the set of all continuous functions $u: D \subseteq \mathbb{R} \mapsto \mathbb{R}$ form an infinite dimensional vector space. Then, we define the distance between two functions $u(x)$ and $v(x)$ to be $\sqrt{\int_a^b (u(x)-v(x))^2dx}$. Now that we have a notion of distance, we can take look at the set $B = \{1, \sin(2\pi x), \cos(2\pi x), \sin(4\pi x), \cos{4\pi x}, \cdots\}$ and grind it through Gram-Schmidt to get an orthonormal set of vectors. It's easy to see that the elements were linearly independent, and we could have started with an arbitrary finite number of them. Now, we just proceed to project our initial function $f(x)$ onto the subspace generated by $B$. The result is $g(x)$ the Fourier series of $f(x)$.

We can now interpret the coefficients of $g(x)$ as "how much of certain frequency of oscillation does the initial function contains". Now to finally define the Fourier transform, a FT is an operator $\mathcal{F}$ which takes in a "nice" function $f(x)$ and spits out two functions $a_n$ and $b_n$ defined on the non-negative integers representing the coefficients of the sines and cos.

In practice, one main problem. We never have continuous data in the real world. To deal with that, we simply discretize the integral into a $N$ part Riemann sum, where $N$ is the number of "equally distanced" data points we have, depending on the context. This is where the "discrete" part of the DFT comes in. Usually, when we perform a DFT, we don't care much about the higher frequency terms because they are usually small.

Now one will never see the Fourier transform under this form because it's so ugly to write out. We bring in Euler's Identity to simplify a few things with complex numbers. We can write:

$$g(x) = \sum_{k=-\infty}^{\infty}c_ke^{2\pi ikx}$$

$$c_k = \frac{1}{2\pi}\int_{-\pi}^{\pi}f(x)e^{-2\pi ikx}dx$$

It is easy, but tedious to work out how the coefficients $c_k$ are related to $a_k$, $b_k$. One thing is for sure, the coefficients with the same $k$ correspond to the same frequencies.

Finally, we discretize and cut off high frequencies. Assume we get a time-series $f_k$ for $k = 1\cdots N$, we apply the DFT:

$$F_k = \frac{1}{N}\sum_{n=N/2+1}^{N/2}f_ne^{\frac{-2\pi ikn}{N}}$$

We go a bit further to make things look nice and substitute $\omega = e^{\frac{2\pi i}{N}}$. So,

$$F_k = \frac{1}{N}\sum_{n=N/2+1}^{N/2}f_n\omega^{-kn}$$

Before I end the post, I'd like to give one application of the DFT. The reason we want to perform the DFT is to distinguish between various frequencies by looking at the corresponding coefficients.

One application of this is filtering out noise from a signal. Usually, noise is of much higher frequency than the signal we wish to process. A simple procedure would be to take the DFT of this signal, multiply the coefficients corresponding to "high" frequencies by zero (the meaning of high depends on the context), and take the inverse DFT (I haven't talked about the inverse DFT, but this post is getting long). This will yield a nice signal devoid of most of the unwanted noise.

Other applications of the DFT will be subject of future posts (and maybe a description of how to perform the DFT efficiently, an algorithm called the Fast Fourier Transform).