Godlike? Not an exaggeration at all!
If we ranked every algorithm, the Fourier transform would absolutely take the crown. How powerful is it?! It basically gave humanity a third eye! It is honestly not something humans should have been able to come up with. Mortals, prepare to worship!
Recommended book
This book (Grokking Algorithms) was carefully picked from a large pile of algorithm books. It
- focuses on understanding the principles behind algorithms,
- replaces obscure formula proofs with vivid examples,
- and has genuinely fun illustrations,
which makes it very friendly to non-specialist developers. My own algorithm tutorial series is also built on Grokking Algorithms as its blueprint.
Where to get it
Besides buying the paper edition, you can also find it on WeRead (WeChat Reading), where unlimited reading cards make it a great deal.
Getting started
This post expands on section 11.3 of Grokking Algorithms. First, let’s meet Fourier: a handsome Frenchman who lived in the 18th century, fought wars alongside Napoleon, served as an official on the imperial payroll, then put down the gun for scholarship β and did rather well at it too, all the way to perpetual secretary of the French Academy of Sciences. A glittering rΓ©sumΓ©: he followed a big shot, and became one himself.
The principle
I really love drinking cola. The Coca-Cola recipe is supposedly a top secret. It is just sugary water β anyone can easily get a finished bottle β yet nobody can reproduce its taste one hundred percent. This process of analyzing a finished product back into its ingredients is called, in technical terms, reverse engineering. It is usually very hard, because it is an open problem.
Sometimes we are interested not only in the ingredients of food, but also in the ingredients of signals: sound, images. Just like guessing the Coca-Cola formula, figuring out the recipe of a sound or an image is a very difficult piece of reverse engineering. But one man did it: Fourier.
We normally look at signals in the time domain: whatever the signal, we observe it along a progress bar, and that seems to be the only way to look at it. Fourier successfully decomposed a signal into a series of simpler signals β sine waves of different frequencies. That gives us the signal’s recipe: once you know the recipe, you can mix signals of various frequencies together and reproduce the original signal. This recipe is the spectrum. Fourier took humanity’s understanding of signals into the frequency domain.
An interesting property
Follow the same recipe, and shredded pork with garlic sauce tastes roughly the same everywhere. A time-domain signal can be converted to the frequency domain, and converted back, it is still the same signal as before (in practice there are tiny differences, but they don’t matter). If the Fourier transform only gave us the recipe of a signal, that would be a bit underwhelming β on top of it, we can do much more interesting things.
High-pass filtering
Very often we need to extract the edges of an image. How would you do it? Trace them with a pen? Let Papa Fourier take you flying β we use a high-pass filter. This “high-pass” is not the company Qualcomm β it means “letting high frequencies pass”. The edges we see in an image are actually pixels that jump between two different color blocks; if you imagine them as sound, those parts are sharper β in other words, higher in frequency. If we convert an image to the frequency domain, hold back the low-frequency signals, let the high-frequency signals through, and then convert back to the time domain, we get an interesting result.
First, please welcome the image field’s famous model β Ms. Lena.
What does her spectrum look like?
The brighter a region, the more of that frequency component there is. The very center of the spectrum is the low-frequency region; the outer ring is the high-frequency region.
We can see a fairly concentrated blob of information in the low-frequency area. Now we dig out the low-frequency information in the center of the spectrum, and the spectrum looks like this:
Convert the frequency-domain signal back to the time domain, and see what happened to Ms. “Lena”?
We get a “line drawing” β the edges of the image, extracted. All we did was a Fourier transform plus a high-pass filter. Magical, isn’t it!
For audio signals, with the Fourier transform we can easily remove low-frequency noise in the frequency domain, or polish the sound. The principle is roughly the same.
No Fourier, no internet
Today, almost all information is eventually digitized, and digitization uses the Fourier transform and its variants. Only with the Fourier transform can signals be identified as concrete components and digitized.
Next time you use a beauty camera or scroll through short videos, remember to give big boss Fourier a double tap!
The code is here.