HN Reader

This is maybe a good first thing to read if you've never heard of the Fourier Transform before, but it makes it sound a great deal more arbitrary and random than it actually is. It might set your understanding back by giving you the illusion that you understand things you don't actually understand, and that would be a shame, because some of those things are more beautiful than a sunrise or a hummingbird.

It would be very sad to lose those treasures by passing them by because you thought you already had them. As the song says:

> When you're young, you're always looking

> On the far side of the hill;

> You might miss the fairest flower

> Standing by your side very still.

And the flowers of Fourier analysis are as fair as the fairest flowers in this universe, or any universe.

https://news.ycombinator.com/item?id=45134843 may be a clue to the hidden beauty, for those who are puzzled as to what I might be talking about.

This video [1] from a visual effects channel (Captain Disillusion) has an excellent visual illustration of how the Fourier tranform works and how its used in visual effects in his video about blurring and unblurring ("ENHANCE!") images.

1. https://youtu.be/xDLxFGXuPEc?feature=shared

As everyone in this thread is sharing links, I'm gonna pitch in, too.

This lecture by Dennis Freeman from MIT 6.003 "Signals and Systems" gives an intuitive explanation of the connections between the four popular Fourier transforms (the Fourier transform, the discrete Fourier transform, the Fourier series, and the discrete-time Fourier transform):

https://ocw.mit.edu/courses/6-003-signals-and-systems-fall-2...

If you like Fourier, you're going to love Laplace (or its discrete counterpart, the z transform).

This took me down a very fascinating and intricate rabbit hole years ago, and is still one of my favorite hobbies. Application of Fourier, Laplace, and z transforms is (famously) useful in an incredibly wide variety of fields. I mostly use it for signal processing and analog electronics.

I have a pet theory that the reason why the FT, and other transforms (generating functions, Mellin/Laplace/Legendre/Haar), are so useful is because many real world functions are sparse and lend themselves to compressed sensing.

The FT, as are many other transforms, are 1-1, so, in theory, there's no information lost or gained. In many real world conditions, looking at a function in frequency space greatly reduces the problem. Why? Pet theory: because many functions that look complex are actually composed of simpler building in the transformed space.

Take the sound wave of a fly and it looks horribly complex. Pump it through the FT and you find a main driver of the wings beating at a single frequency. Take the sum of two sine waves and it looks a mess. Take the FT and you see the signal neatly broken into two peaks. Etc.

The use of the FT (or DCT or whatever) for JPEG, MP3 or the like, is basically exploiting this fact by noticing the signal response for human hearing and seeing it's not uniform, and so can be "compressed" by throwing away frequencies we don't care about.

The "magic" of the FT, and other transforms, isn't so much that it transforms the signal into a set of orthogonal basis but that many signals we care about are actually formed from a small set of these signals, allowing the FT and cousins to notice and separate them out more easily.

So weird, I was just reading this article yesterday. I did an undergrad in physics and really miss this stuff. Ended up getting nostalgic and watching 3 blue 1 brown videos while drinking tequila.

> Fourier argued that the distribution of heat through the rod could be written as a sum of simple waves.

How do you even begin to think of such things? Some people are wired differently.

To add another suggestion for understanding the Fourier transform, personally the first explanation that ever clicked with me was the Aho/Hopcroft/Ullman algorithms textbook.

Rather than talking about sine and cosine waves, they motivate the Fourier transform entirely in terms of polynomials. Imagine you want to multiply two polynomials (p(x) and q(x)). The key is to recognize that there are two ways to represent each polynomial:

1. "Coefficient form," as a set of coefficients [p_0, p_1, p_2, ..., p_d] where p(x) = p_0 + p_1x + p_2x^2 + ... + p_dx^d, OR

2. "Sample form," as a set of sampled points from each polynomial, like [(0, p(0)), (1, p(1)), (2, p(2)), ..., (d, p(d))]

Now, naive multiplication of p(x) and q(x) in coefficient form takes O(d^2) scalar multiplications to get the coefficients of p(x)q(x). But if you have p(x) and q(x) in sample form, it's clear that the sample form of p(x)q(x) is just [(0, p(0)q(0)), (1, p(1)q(1)), ...], which requires only O(d) multiplications!

As long as you have enough sample points relative to the degree, these two representations are equivalent (two points uniquely defines a line, three a quadratic, four a cubic, etc.). The (inverse) Fourier transform is just a function that witnesses this equivalence, i.e., maps from representation (1) to representation (2) (and vice-versa). If the sample points are chosen cleverly (not just 1/2/3/...) it actually becomes possible to compute the Fourier transform in O(d log d) time with a DP-style algorithm (the FFT).

So, long story short, if you want to multiply p(x) and q(x), it's best to first convert them to "sample" form (O(d log d) time using the FFT), then multiply the sample forms pointwise to get the sample form of p(x)q(x) (O(d) time), and then finally convert them back to the "coefficient" form (O(d log d) using the inverse FFT).

Always blew my mind that every signal can be recreated simply by adding different sine waves together.

Fourier's fundamental discovery was that the most natural building blocks for periodic functions are complex exponentials. These in turn were based on Euler's identity, linking complex exponentials to sines and cosines, and which is algebraic (easy to differentiate, integrate, manipulate) and also encodes rotations and waves. So, a good reason to study complex analysis and include it in the engineering maths program.

This setup then allowed Fourier to take the limit of the Fourier series using a complex exponential expression. But keep in mind, this is all in the context of 19th century determinisitic thinking(see Fourier's analysis of the heat equation 1807, and Maxwell's treatise on 'Theory of Heat' c. 1870s), and it ran into real-world limits in the late 19th century, first with Poincare and later with sensitive dependence on initial conditions. . Poincare showed that just because you have a deterministic system, you don't automatically get predictability. Regardless this Fourier transform mathematical approach worked well in astronomy (at least at solar-system scale) because the underlying system really was at least quasiperiodic - essentially this led to prediction of new planets like Neptune.

But what if you apply Fourier transform analytics to data that is essentially chaotic? This applies to certain aspect of climate science too, eg, efforts to predict the next big El Nino based on the historical record - since the underlying system is significantly chaotic, not strictly harmonic, prediction is poor (tides in contrast are predictable as they are mostly harmonic). How to treat such systems is an ongoing question, but Fourier transforms aren't abandoned, more like modified.

Also, the time-energy quantum mechanics relation is interesting though not really a pure QM uncertainty principle, more like a classical example of a Fourier bandwidth relation, squeeze it on one axis and it spreads out on the other - a nice quote on this is "nothing that lives only for a while can be monochromatic in energy." Which sort of leads on to virtual particles and quantum tunneling. (which places a size limit of about 1 nm on chip circuitry).

The bottom line is that if you're applying elegant and complex mathematical treatments to real-world physical problems, don't forget that nature doesn't necessarily follow in the footsteps of your mathemetical model.

What always bothered me when trying to "feel" Fourier transforms is that to compute the oscillations, you need to wait some time. Mathematically, the transformation includes computing integrals. So it's tricky to understand how you compute the Fourier decomposition for a stream. Illustrations always show the whole signal over time but in real life you get the signal progressively. I'd be eager to read more on this.

For those interested in an extension from this article, https://howthefouriertransformworks.com/ has a beautifully kitsch set of videos on the topic.

They do a really good job at breaking down the fundamental knowledge needed to build an understanding.

As usual, BetterExplained.com has it covered: https://betterexplained.com/articles/an-interactive-guide-to...

I think the best explanation and understanding I received about Fourier Transform was from studying linear algebra.

The Fourier Transform equation essentially maps a signal from the time domain onto orthogonal complex sinusoidal basis functions through projection.

And the article does not even mention this. =)

Reading the comments, it seems there are very few electrical engineers in hacker news.

Amazing.

Until I read this article I didn't properly understand Fourier transforms (I didn't know how image compression bitmaps were derived), now it's opened a whole new world - toying with my own compression and anything that can be continuous represented as it's constituent parts.

I can use it for colour quantisation too possibly to determine main and averaged RGB constituents with respect to hue, allowing colour reduction akin to dithering, spreading the error over the wave instead and removing the less frequent elements.

It may not work but it'll be fun trying and learning!

Learning about the FT in engineering and how it can represent pretty much any repeating signal was mind blowing. It was the culmination of so much learning in mathematics that brought me to that wow moment.

IANAMathematician, but I've tried to come up with a metaphor which I hope isn't too wrong:

1. You've start with a signal fluctuating going up and down, and it's on a strip of little LEDs labeled from -1 to +1.

2. You mount that strip to a motor, and spin it at a certain rate. After a while the afterimages make a blob-shape.

3. For each rotation rate, measure how much the shape appears off-center.

In this way you can figure out how much the underlying signal does (or doesn't) harmonize with a given rotation hertz.

Before computer was ever invented we learned to make Fourier analysis of complex circuitry by hand. Huge matrixes and sliderules. It was most horrible torture, but bloody nazies of Helsinki Polytechnic insisted we must learn to do this without errors and also fast.

When I first time used computer for this task around 1974 on clanky ASR-33, I felt totally abused and brain-raped.

See also its windowed version, https://en.wikipedia.org/wiki/Short-time_Fourier_transform

Bill Hammack The Engineer Guy has a video series on this subject.

https://www.youtube.com/watch?v=6dW6VYXp9HM

See also

"The LCT generalizes the Fourier, fractional Fourier, Laplace, Gauss–Weierstrass, Bargmann and the Fresnel transforms as particular cases."

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

One thing I find fascinating about Fourier analysis is the way the trigonometric Fourier series played such a central role in “breaking mathematics”[1] and the crisis that led to providing a rigorous basis for limits and continuity and all the other stuff that is now called real and complex analysis.

Cauchy had just proved that the limit of the sum of an infinite set of continuous functions was itself continous, and then along came Fourier with “are you sure about that bro?” and showed that you could take the infinite sum of very clearly continuous functions (just sine and cosine) and approximate something like a sawtooth function (which was very obviously discontinous) as closely as you like.

[1] by which I mean making obvious the fact that they had been proceeding for 100+ years using calculus without a rigorous basis.

Speaking of the Fourier transform, I recommend these visual explorable explanations: https://injuly.in/blog/fourier-series/index.html and https://www.jezzamon.com/fourier/

3Blue1Brown made a video with great visualizations: https://www.youtube.com/watch?v=spUNpyF58BY

Such a shame. In an otherwise well-written article, the author mentions Cooley and Tukey's discovery of the FFT, but without mentioning that Gauss discovered it first, among others, each of whom approached the same idea from different directions.

The Wikipedia FFT article (https://en.wikipedia.org/wiki/Fast_Fourier_transform) credits Gauss with originating the FFT idea later expanded on by others, and correctly describes Cooley and Tukey's work as a "rediscovery."

Applying FT to images is a great way to see the world very differently, as if through an alien's eyes (or Geordi's visor from ST TNG!). A kind of stimulated out-of-the-box thinking. Dense features like fur or hair manifest as high-frequency components and eventually you start to develop an intuition for their patterns in the magnitude / power spectrums.

Shameless plug: If you are interested in Fourier Transform and signal processing you might enjoy my somewhat artistic 3D visualisation of the fourier transform as well as the fractional fourier transform [1]

(Fractional fourier transform on the top face of the cube)

And for short time fourier transform showing how a filter kernel is shiftes across the signal. [2]

[1]: https://static.laszlokorte.de/frft-cube/

[2]: https://static.laszlokorte.de/time-frequency/

This is a great playlist by 3b1b about the subject:

https://www.youtube.com/watch?v=spUNpyF58BY&list=PL4VT47y1w7...

Kind of a tangent but why are there so many articles and videos popularizing the Fourier transform and practically none for the Laplace transform? The first person to do a well done 3Blue1Brown style video that focuses on intuition and visualization would probably be an overnight sensation (well, among engineers at least).

> A compression algorithm can then remove high-frequency information, which corresponds to small details, without drastically changing how the image looks to the human eye.

I slightly object to this. Removing small details = blurring the image, which is actually quite noticeable.

For some reason everyone really wants to assume this is true, so for the longest time people would invent new codecs that were prone to this (in particular wavelet-based ones like JPEG-2000 and Dirac) and then nobody would use them because they were blurry. I think this is because it's easy to give up on actually looking at the results of your work and instead use a statistic like PSNR, which turns out to be easy to cheat.

I love the content here but the website hijacks my default mouse highlight and it does not allow me to right click and save highlights which is mildly annoying. Only me?

I found the 3Blue1Brown explanation to be more intuitive to understand, but this article has more practical examples/details.

Here's the 3Blue1Brown explanation:

https://www.youtube.com/watch?v=spUNpyF58BY

https://www.3blue1brown.com/lessons/fourier-transforms

While we are talking about fun facts of the Fourier transform, the transfer function of the DFT is a sinc. That's how OFDM works, it performs an FFT on parallel input symbol streams. If you look at the spectrum of your signal it's sinc (approximately because they are truncated) channels spaced at 1/symbol rate which don't exhibit (theoretically if they weren't truncated) any interchannel interference.

The most shocking thing for me was the realization that frequency and wavelength are kind of dual forms. Ofcourse, every concept and thing that comes into existence does so only in the context of it's opposite or dual form. But recognizing that form is genius. 3b1b video goes a bit deeper.

Also a related fact is that the rate of change of a sine wave is itself shifted by pi/2, while the exponential curves need no shifting. I'm not a professional in these matters, but I guess there is a deeper connection between the rate of change and the static world.

>one man’s mathematical obsession gave way to a calculation that now underpins much of mathematics and physics

Underpins much of mathematics, science and engineering

My favorite algorithm (just for the name) is [Lomb-Scargle Periodogram](https://docs.astropy.org/en/latest/timeseries/lombscargle.ht...) which is a method for performing a Fourier transform on irregularly sampled data.

I didn’t have time to read the article, but it’s cool that the position operator and the momentum operator in quantum mechanics are fourier transforms of one another.

The Fouriertransform is a change of bases in infinite dimensional space.

That sounds complicated but if you look at the integral the exponential kernel is essentially a continuous “matrix” and the function you are integrating over that kernel is a continuous vector.

This observation on can be a guide to better understand infinite dimensional Hilbert spaces ( inner product space + stuff) and is one of the core observations in quantum mechanics where it’s part of the particle-wave concept as it transforms location space -> momentum space.

Can somebody eli5, im an amateur. How does the transform know the frequencies of the output. Do you have to specify a number n, and then it decomposes it into n frequencies. Or do you give it a list of frequencies, and then it decomposes the coefficient or amplitude or something for each?

I guess what i want to know, in the examples it always shows like 3 or 4 constituents frequencies as output, but why not hundreds or a million? Is that decided upfront /paramtetizable?

The article isn't helpful, it just says something like "all possible frequencies".

> The waves that oscillate more quickly — meaning they have more energy

Isn't this essentially a quantum-mechanical concept?

All these comments and no Steinmetz mention. The original papers he wrote applying the transforms to electrical engineering work are so genius and simplifying for the craft, and he's such a nicer person for one of the founders of the field of EE. Also the origin of that old story about $10 for hitting the machine with a hammer $9990 knowing where to hit it, from what I can gather.

Everyone loves the fourier transform because it's easy to understand but everyone ignores the laplace transform, which is much more beautiful, imo, and quite related.

There's a lot of great Fourier visualizations out there (3Blue1Brown has a series on it as well). A great intuition pump would be a game where the player has to recreate a waveform given to them, by toggling on/off switches for each fundamental frequency (and phase).

Has anyone ever seen something like that?

What really gets me going though is quaternions...

Isn’t the Fourier series fundamentals generally a required course in undergraduate college EE field?

For lossy compression, turns out a sinusoidal (typically DCT) composition maximizes energy compaction and compress ability. A proof that this is true for AR-processes was a key realization for me. That you get a nice and intuitive domain to work with (modify frequencies) is a nice bonus on top :)

Fourier transforms are useful in applications like avoiding moire when downscaling manga and reducing rainbow artifacts in color eink manga. All in kindle comic converter.

One of my favorites.

A change of basis.