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]
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.
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 :)
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).
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):
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).
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.
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).
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.
> 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.
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.
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.
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.)
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.
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."
64 comments
[ 3.3 ms ] story [ 72.0 ms ] thread(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 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 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 :)
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).
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...
Has anyone ever seen something like that?
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. =)
Underpins much of mathematics, science and engineering
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.
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.)
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.
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."