When I did EE, didn't have access to any kind of computer algebra system. Have 'fond' memories of taking Laplace transform transfer functions and converting to z-transform form. Expand and then re-group and factor. Used a lot of pencil, eraser and line printer fanfold paper for doing the very basic but very tedious algebra. Youngsters today don't know how lucky.. (ties onion to belt, etc., etc.)

Years ago, I often struggled to choose between Amazon products with high ratings from a few reviews and those with slightly lower ratings but a large volume of reviews. I used the Laplace Rule of Succession to code a browser extension to calculate Laplacian scores for products, helping to make better decisions by balancing high ratings with low review counts. https://greasyfork.org/en/scripts/443773-amazon-ranking-lapl...

When I first learned Laplace transform in university, it was my goto for differential equations of any kind. I was even naive enough to believe well this is a solved problem now. Eventually found out this wasnt the case after studying PDEs. Its still my favourite transform. Immensely useful not to mention the whole method of moments in random variables is basically laplace transform.

I don't like Fourier transform but for petty reasons. In the engineering exams, I messed up a Fourier Transform calculation and ended up just a few points short of a perfect score. Hate it ever since :)

When I think of Laplace Transforms I always think of control theory - poles, zeros etc.

The so-called "Z transform" for discrete sequences is really just a misnomer for the actual method of generating functions (and formal power-series/Laurent-series). You just write a discrete sequence as a power series in z^(-1).

Essentially that's what electrical/electronics engineering is about.

Then there's the whole mindfuck of fractional order Fourier (and other) transforms.

I wonder what happened to Wavelet transforms? The were very popular years ago, and now one never hears about them.

Excellent! Thanks!

As usual, 3 Blue 1 Brown delivers: https://youtu.be/spUNpyF58BY?si=nSqHf_3zbhyu9YGd

As mentioned by other commenters, a reason for the FT's dominance in particular is because sine, cosine, and complex exponentials are the eigenfunctions of the derivative operator. Since so many real-world systems are governed by differential equations, the Fourier Transform becomes a natural lens to analyze these systems. Sound waves are one (of many) examples.

And there's another good reason why so many real-world signals are sparse (as you say) in the FT domain in particular: because so many real-world systems involve periodic motion (rotating motors, fly's wings as you noted, etc). When the system is periodic, the FT will compress the signals very effectively because every signal has to be harmonic of the fundamental frequency.

On the simplest end of that spectrum, Taylor series are useful because many real-world dynamics can be approximated as a "primarily linear behavior" + "nonlinear effects."

(And cases where that isn't true can still be instructive - a Taylor series expansion for air resistance gives a linear term representing the viscosity of the air and a quadratic term representing displacement of volumes of air. For ordinary air the linear component will have a small coefficient compared to the quadratic component.)

As you noted, it’s about what’s important to us. The physical function may or may not be sparse, but our brain model is guaranteed to be sparse. A note played on a violin is anything but a sine function, yet our brains associate it with a single idealized tone. Our world model is super compressed.

While I like CD's works, I would say "CD / Blur" is the least informational of all the CD slash series. I guess it's a fun and more accessible option, but it certainly lacks depth compared to something like 3B1B's video on FT.

I found this video from 3Blue1Brown more informative in terms of mathematics involved:

https://youtu.be/spUNpyF58BY?feature=shared

Edit: In fact it was already mentioned in the comments, but I haven't noticed

The Carl Sagan bit is also an amusing tribute.

Thanks a lot for all of this ! https://tools.laszlokorte.de/

If I might also plug ‘the Atlas of Fourier Transforms’. If your interested in understanding building intuition of symmetry and phase in fourier space, the book illustrates many structures.

I love the visualization! Thanks for sharing.

How do you compute the fractional FT? My guess is by interpolating the DFT matrix (via matrix logarithm & exponential) -- is that right, or do you use some other method?

Fantastic! Thanks!

As they say, everything in modern math is named for the 2nd person to discover it after Gauss.

Yes, bad article to omit that. It is such a cool fun fact. Gauss was unreal.

I’ve dabbled in explaining the FT some, and I think there’s an important trait of that video that needs to be highlighted: it’s a superb demonstration of what the Fourier transform does, mechanically, but it does not at all try to explain why it works in the places we usually apply it or how (having, admittedly, a thoroughly anachronistic mathematical background) you could have invented it.

To be extra clear: it’s a very good video and you should watch it if you don’t have a feel for the Fourier transform. I’m just trying to proactively instil a tiny bit of dissatisfaction with what you will know at the end of it, so that you will then go looking for more.

I don't know/remember the historical derivation, but the story you might get in a class goes something like:

Energy can't be created or destroyed, so it follows a continuity equation: du/dt + dq/dx = 0. Roughly, the only way for energy to change in time is by coming from somewhere in space. There are no magic sources/sinks (a source or sink would be a nonzero term on the right).

Then you have Fourier's law/Newton's law of cooling: heat flows proportional to temperature difference, from high to low: q = -du/dx.

Combining these, you get the heat equation: du/dt = d^2 u/dx^2.

Now if you're very fancy, you can find deeper reasons for this, but otherwise if you're in engineering analysis class, just guess that u(t,x)=T(t)X(x). i.e. it cleanly factors along time/space.

But then T'(t)X(x)=X''(x)T(t), so T'(t)/T(t) = X''(x)/X(x). But the left and right are functions of different independent variables, so they must be constant. So you get X''= λX for some lambda. But then from calc1, X is sin/cos.

Likewise T' = λ T so T is e^-λt from calc 1.

Then since it's a linear differential equation, the most general solution (assuming it splits the way we guessed) is a weighted sum of any allowable T(t)X(x), so you get a sum of exponentially decaying (in time) waves (in space).

It didn't come completely out of nowhere, Euler and Bernoulli had looked at trigonometric series for studying the elastic motion of a deformed beam or rod. In that case, physical intuition about adding together sine waves is much more obvious. https://en.wikipedia.org/wiki/Euler%E2%80%93Bernoulli_beam_t...

Other mathematicians before Fourier had used trigonometric series to study waves, and physicists already understood harmonic superposition on eg a vibrating string. I don't have the source but I believe Gauss even noted that trigonometric series were a solution to the heat equation. Fourier's contribution was discovering that almost any function, including the general solution to the heat equation, could be modelled this way, and he provided machinery that let mathematicians apply the idea to an enormous range of problems.

I think he was very familiar with differential equations and series expansions and the "wild west" stage of calculus in general. The frontier of cool and interesting mathematics has moved a lot in 200 years.

Great explanation, thanks for sharing

Back in my uni days I did not get why that works. Why are sine waves special?

Turns out... they are not! You can do the same thing using a different set of functions, like Legendre polynomials, or wavelets.

It makes more sense when you approach it from linear algebra.

Like you can make any vector in R^3 `<x,y,z>` by adding together a linear combination of ` <1,0,0> `, ` <0,1,0> `, ` <0,0,1> `, turns out you can also do it using `<exp(j2pi0/30), exp(j2pi0/31), exp(j2pi0/32)>`, `<exp(j2pi1/30), exp(j2pi1/31), exp(j2pi1/32)>`, and `<exp(j2pi2/30), exp(j2pi2/31), exp(j2pi2/32)>`.

You can actually do it with a lot of different bases. You just need them to be linearly independent.

For the continuous case, it isn't all that different from how you can use a linear combination of polynomials 1,x,x^2,x^3,... to approximate functions (like Taylor series).

Taking the concept to a 2d path: https://www.myfourierepicycles.com

And, with your own drawing: https://gofigure.impara.ai

I swear I read in a text book once that Fourier discovered this while a boat. He looked out at the waves on the ocean and saw how there were many different sized waves combining to make up the larger waves. I could never find it again, but that visual helped me understand how the Fourier transform works.

Only if it is band-limited.

Well, there are use cases for lossy compression as well as non-lossy, and nobody is saying they are the same. If you really need to heavily compress to reduce file size or transmission bandwidth then you'll likely need to use a lossy CODEC, so the question then becomes how can you minimize the reduction in perceived quality of whatever you are compressing (photos, video, audio), which comes down to how these various human sensory/perceptual systems work.

For vision we are much more sensitive to large scale detail (corresponding to low frequency FFT components) than fine scale detail (corresponding to high frequency components), so given the goal of minimizing reduction in perceived quality this is an obvious place to start - throw away some of that fine detail (highest frequency FFT components), and it may not even be noticeable at all if you are throwing away detail at a higher level of resolution than we are able to perceive.

It turns out that human vision is more sensitive to brightness than color (due to numbers of retinal rods vs cones, etc), so compression can also take advantage of that to minimize perceptual degradation, which is what JPEG does - first convert the image from RGB to YUV color space, where the Y component corresponds to brightness and the U,V components carry the color information, then more heavily compress the color information than brightness by separately applying FFT (actually DCT) to each of the Y,U,V components and throwing away more high frequency (fine detail) color information than brightness.

But, yeah, there is no magic and lossy compression is certainly going to be increasingly noticeable the more heavily you compress.

You might be surprised to learn that videos and many images are broken down into brightness + color vectors. Brightness is typically done near the resolution of the image (eg 4K) but color is often 1/4 of that. That’s literally blurring the picture.

Check out https://en.m.wikipedia.org/wiki/Short-time_Fourier_transform

This is the "Fourier transform" that is most often used, in practice in computing.

A longer window length gives lower frequency resolution, but longer latency.

For a stream, you use a sliding window to compute the FFT. The size of the window of course limits the lowest frequency range that you can 'see', same for the highest frequency through the time quantization that digital data usually has. So there will be an upper and lower frequency limit, beyond those limits the results are meaningless.

And the window of course creates a latency, which is sometimes relevant for realtime audio filtering by FFT.

The keyword you're looking for is time-frequency analysis and the main associated tool is the short-time Fourier transform(s). This is the theory underlying spectrograms and all those niceties!

As I remember intuitively, it's a convolution over a time window. The size of the time window limits the frequencies that can be detected.

You do it in short windows, so you get eg. 512 samples and then run a short FFT. Or you can do longer windows that overlap, so e.g. hop by 512 but take 1024, more samples gives you more accurate results.

Steinmetz is an unsung hero of tech, except to well-educated EE's.

Was he a dwarf or a hunchback? I seem to recall a physical setback.

That is a very true comment. Electrical Engineering for example would be nothing without Laplace (which is more or less an even more general Fourier).

I was going to post this link as well. That site has really helped me understand many things.

Best explanation I got was from 3 blue 1 brown! It’s what you said, but with nice visuals

Almost every paragraph of this article says the same thing but in different ways.

Maybe they are EE’s, who just happen to still find some joy in the stuff from their intro classes. Sometimes little things can still make us happy, after all.

I'll try.

Suppose you blinde, and are on one side of a black picket fence. Let's say the fence uprights are 1" wide, and 1" apart.

If you aim a light meter at the fence, it will sum up all the light of the visible slices of the background. (This meter reads its values out loud!)

Suppose the background is all white - the meter sees white slices, and get a 50% reading (because the fence stripes are black). It's as high as you can get.

Now move the picket fence half an inch to the left - still all white, still a 50% reading. Now you know the background is 100% white, no other colors.

But if when you move it, black stripes are exposed, then the meter reads 0%, and you know that the background is 50/50 white and black, in stripes.

Congratulations! You've just done a Fourier transform that can detect the difference between 0-frequency and a 1"-striped frequency pattern. In reality, you're going to continuously move that fence to the left, watching all the time, but this is simple.

But instead, imagine you got readings of 40% and 10%. What kind of pattern is that? Gray stripes? White stripes that aren't as wide as the fence posts? You'll have to build another fence, with another spacing - say 1/2" fence posts 1/2" apart. Repeat.

If you take N samples of a real signal you will get N/2+1 bins of information from the DFT, covering 0Hz out to about half the sampling rate.

The bins do not actually measure a specific frequency, more like an average of the power around that frequency.

As you take more and more samples, the bin spacing gets finer and the range of frequencies going into the average becomes tighter (kind of). By collecting enough samples (at an appropriate rate), you can get as precise a measurement as you need around particular frequencies. And by employing other tricks (signal processing).

If you graph the magnitude of the DFT, signals that are a combination of power at just a few frequencies show just a few peaks, around the related bins. Eg a major chord would show 3 fundamental peaks corresponding to the 3 tones (then a bunch of harmonics)

https://en.wikipedia.org/wiki/Fourier_transform#/media/File:...

So you detect these peaks to find out what frequency components are present. (though peak detection itself is complicated)

Maybe this will help https://dsego.github.io/demystifying-fourier/

In a discrete Fourier transform, the number of frequencies you get out is the number of datapoints you have as input. This is because any frequencies higher than that are impossible to know (ie, they are above the sampling frequency).

But in the continuous Fourier transform, the output you get is a continuous function that's defined on the entire real line.

An interesting mechanical analogy! In this example, the "integration" is done by the eye and perhaps by the LEDs depending on their type. But it's more akin to the Gabor Transform than Fourier, as there is locality in time.

Sounds like a variation on the mechanical strobe tuner.

It's going from the frequency domain (parallel symbol streams) to the time domain (multi-carrier RF), so it's using the inverse FFT.

My take on this is that Fourier is easier to understand, has more immediate and relatable practical applications, and can be explained to "common folk" with just-enough sophistication and some tangible analogies (like the wool picture from the article).

Explaining Laplace to solve differential equations with analogies it's a bit more... complicated.

I created a small piece trying to build intuition, my approach was to think of it as probing with test signals, so instead of recreating a waveform, it's more poking at it with sines and seeing how well the test sine matches the target signal.

https://dsego.github.io/demystifying-fourier/

They are quite related, but the Fourier transform seems far more beautiful and generalizable: you can do 2-d, 3-d, etc transforms, and they automatically respect the symmetries of the problems (e.g. rotating the coordinate system rotates the Fourier transform in a corresponding way; frequencies and wave-vectors have meanings). This fully extends to any "nice" abelian group satisfying minor technical conditions, where the mapping is to it's dual group. It even mostly extends to non-abelian groups (representation theory), though some nice properties are lost.

The Laplace transform shines in having nicer convergence properties in some specific cases. While those are extremely valuable for control problems, it really is a much more specialized theory, not nearly as widely applicable. (You can come up with n-d versions. The obvious thing to do is copy the Fourier case and iteratively Laplace transform on each coordinate; the special role of one direction either directly in the unilateral case, or indirectly via growth properties in the bilateral case make it hard to argue that this can develop to something more unifying; the domain isn't preserved under rotation.)

? It's true for all waves in all media.

Of course. It's taught in both mathematics courses as well as engineering. The Fourier transform and it's digital domain cousin, the discrete Fourier transform play such a fundamental role across nearly every engineering discipline as well as physics and many other scientific areas, you cannot get through school without learning about them.

Yes, but how many software engineers remember any of that? Most aren't using it.

Hmm I always viewed it as sum over orthogonal bases. Sine/Cosine is choice, while there can be many other bases, like Legendre polynomials. Can you explain more how FT is linked to 'a sum over equivalence classes'?

This kind of statement is too vague to be useful. I even know all the words in there and I still don't know what you mean.

On your site you make the claim that: "Our thesis is that there is 100 years of physics and math research that has gone unnoticed by the CS/ML communities and we intend to rectify that."

Extraordinary claims require extraordinary evidence. Especially considering that a decent fraction of the CS/ML researchers that I know have solid physics and math backgrounds. Just of the top of my head, Marcus Hutter, David MacKay, Bernhard Scholkopf, Alex Smola, Max Welling, Christopher Bishop, etc. are/were prominent researchers with strong math and physics backgrounds. More recently Jared Kaplan and Dario Amodei at Anthropic also have physics backgrounds, as well as plenty of people at DeepMind.

To claim that you have noticed something in "100 years of physics and math research" that all of those people (and more) have missed and you didn't is pure hubris.