Application of the FFT

Question

A discrete Fourier transformation of N-th order is the map $F:\mathbb{C}^N\to\mathbb{C}^N$ given by $$w=Fz\qquad w_k=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\zeta_N^{jk}z_j,$$ where $\zeta_N=e^{-\frac{2\pi i}{N}}$.

Now we can calculate the $w_k$ by the FFT for $N=2n$ by $$w_{2m}=\frac{1}{\sqrt{N}}\sum_{j=0}^{n-1}\zeta_n^{jm}z_j^g, z_j^g=z_j+z_{j+n}\qquad w_{2m+1}=\frac{1}{\sqrt{N}}\sum_{j=0}^{n-1}\zeta_n^{jm}z_j^u, z_j^u=\zeta_{2n}^j(z_j-z_{j+n})$$

for $m\in\{0,...,n-1\}$.

Now I understand that this FFT gives a powerful tool to reduce the calculation to two coefficients of half the order $\frac{N}{2}$. You can also iterate it for $N=2^n$.

But what is it good for? My question is maybe a soft one. I mean for given $z\in\mathbb{C}^N$ I can calculate the $w\in\mathbb{C}^N$ and the FFT helps me doing it effectively. But why should I do this?

1.) What is the relevance of calculating $w$ for a given $z$?

2.) What is the intuition behind the discrete Fourier transformation? What does it do with my initial values for $z$?

I hope my question is specific enough. If not, leave a comment.

Answer 1

While the standard Fourier transform (integral) truly belongs to mathematics, I believe that the DFT escapes to engineering. I tend to teach it the following way (I am an electrical engineer by training):

1. We have the truly amazing integral Fourier transformation, which for instance diagonalizes convolution
2. We have instruments (sensors for instance) that have, hopefully, a linear response (they don't saturate) and we hope their functions don't alter too fast: they are time-invariant, and act like convolutions. So continuous complex sines (cisoids) are their eigenvectors
3. We humans and computers can only work on finite sequences with a finite number of operations (and computing exact integrals)

So what can we do to have something "discrete" and "finite" with all the nice properties of the Fourier transform? This is difficult, since the discrete and the continuous are different, and corresponding properties don't always match. And somehow, we will have to lose something. But DFT is the closest-as-we-can to the Fourier transform (FT) for us computers and humans.

So:

1. First we discretize indices in the primal domain ($t$ for $s(t)$) to get $s_n=s(nT)$ for some $T$, and we get the discrete time Fourier transform (DTFT). We now suppose we only have $N$ points in the sequence $s_n $. Continuous time $t$ is now gone. We verify that we keep what we can from the FT properties (shift, inversion, orthogonality, Parseval-Plancherel, etc.). We can now work with discrete sequences or series $s_n\to S(\omega)$. We realize that there is periodicity involved, and we try to work on a circle of radius $1$ in the complex plane.
2. Second, we discretize the dual variable $\omega$. We realize that if we take only $N$ points regularly around the unit circle in the dual domain, then under some conditions, we now have a linear transform that is orthogonal, mimics the FT as-close-as-it-can. Continuous frequency $f$ is now gone.

You now have your DFT. With respect to all the collateral damages induced by the double discretization, DFT now does a great job as the stunt performer for the FT: it does all the hard computing work while the FT gets the credits.

But is now can be used and studied for its own right, see for instance "Discrete time and discrete Fourier Transforms", from "The Transforms and Applications Handbook", Ed. Alexander D. Poularikas, 2000.

So, to wrap it up:

1. What is the relevance of calculating $w$ for a given $z$? Detect periodicities in novel series, compute operators faster (because of the FFT), etc. what you would have expected to use if the series were continuous
2. What is the intuition behind the discrete Fourier transformation? Compute as a human or a computer, as detailed above

But remember Fourier did invent the theory to solve the heat equation (and somehow invented distributions, as he almost stumbled upon the Dirac delta operator). DFT is useful for differential equations too.

And later, came the wavelets... (cliffhanger).

Answer 2

Many functions you can measure or estimate in science and engineering can benefit from a fourier frequency description, and digital sampling is done in discrete values (therefore the Discrete and not Continous). Well known examples:

1. Pure music tones are sines.
2. Periodic functions get a very specific Discrete Fourier Transform - at least if the sampling is aligned with the period time. Many functions in nature are periodic - heartbeats, rotating machinery. DFT provide a natural description for them.

But also it's calculational properties:

1. Convolutions become products in the Fourier domain, and
2. Differentiation has complex exponentials as it's eigenfunctions.

So practical calculations done (or undone) by convolution can benefit from the DFT but also in trying to solve differential equations.