About the author:
Daniel is CTO at rhome GmbH, and Co-Founder at Aqarios GmbH. He holds a M.Sc. in Computer Science from LMU Munich, and has published papers in reinforcement learning and quantum computing. He writes about technical topics in quantum computing and startups.
jrnl · home about list ventures publications LinkedIn Join my Slack

# FFT of a line is another line

The fast Fourier transform of a vertical line is a horizontal line. WTF?

One interpretation of the FFT is summing up many sine curves, i.e. for a given function there exists some infinite amount of sine curves that, when added up, can represent an approximation of the function. The function that we want to represent in the picture below1 is a popular example - the square wave.

Another point to understand: The power of the frequency tells us the weighting of one sine curve. High power? That sine curve is important.

Now, back to the vertical line. The FFT is telling me: Sum up the sinues curves of ALL frequences there exist. And that shall result in a vertical line. It needs ALL frequences to represent that line, and at the same power. But why?!

And wait, those are sine curves.. Should we not get some kind of residuals around the vertical line, resulting in something similar to the shape of Mt. Fuji? I can immediately tell you - this is completely wrong. You need to think in an infinite sense. Assume we want to start creating such a vertical line.

The brown curve on top is the sum of all sine curves. As you can see (on the right side I simply shifted the curves a bit on the yy axis for easier comprehension), a line appears! The trick here is that different sine curves cancel each other out. But coincidentally, there is a point where all curves do the same thing: They are at their local maximum. This is where our vertical line forms. By the way, don't mind the yy axis, the wave can be normalized to 00 back from 2020 easily. This is the basic idea and can be followed into infinity.

Now, to actually get a straight vertical line, apparently all frequencies have exactly the same power, going as far as to even depending on the height of the line. If its height is 11 , the line in frequency domain lies at y=1y = 1 . For 22 , it is 22 . And so on. I have not been able to understand intuitively yet why this is the case. However, in the following, the mathematical proof shows that this is indeed always the case for any given vertical line.

First a definition of the DFT is needed:

Xk=n=0N1xnei2πNknX_k = \sum_{n = 0}^{N - 1}x_n * e^{\frac{-i2\pi}{N}kn}

Assume the time domain data is as follows: [1,0,...,0][1, 0, ..., 0] . It is immediately clear that only the first summand is non-zero, since the rest is multiplied with xn=0x_n = 0 . Additionally, for the first summand, since n=0n = 0 and x0=1x_0 = 1 , it holds that 1e0=11 * e^0 = 1 and thus XkX_k is 11 . This holds for all kk .

This works analogously for all multiples, such as [9,0,...,0]:9e0=9[9, 0, ..., 0]: 9 * e^0 = 9 .

>>> import numpy as np
>>> np.fft.fft([9, 0, 0, 0, 0, 0, 0, 0])
array([9.+0.j, 9.+0.j, 9.+0.j, 9.+0.j, 9.+0.j, 9.+0.j, 9.+0.j, 9.+0.j])

Further references:

https://www.ritchievink.com/blog/2017/04/23/understanding-the-fourier-transform-by-example/

https://en.wikipedia.org/wiki/Discrete_Fourier_transform

http://www.jezzamon.com/fourier/

Published on