The Most Underrated Algorithm

The 2-minute brute-force explanation of Fourier transforms in a recent Veritasium video was my "aha!" moment. [VIDEO]

That video did the same for me. I also like the reducible video for Fast Fourier Transforms as well as the Veratasium piece that shares some fun history. Reducible - FFTs the most ingenious algorithm ever [LINK] Veritasium - The Most Important Algorithm of All Time [VIDEO]

If you have 26 minutes spare, Veritaserum's video [0] on the history of FTs and FFTs is quite good. Effectively, a Fourier Transform can turn a signal into its underlying frequencies using a neat property of maths. For a piece of music, say, you could produce a spectrogram [1] – Foobar2000 [2] has a nice one built in – to visualise the frequency of music with time. In general, this is all sorts of useful applications any time you have a signal – electronics, climate physics, astrophysics, detecting nuclear explosion testing underground, and so on. It's essential to modern medical imaging, and a whole bunch of differential equations can be solved a lot faster by using this. The FFT takes the naive O(N^2) algorithm and makes it O(n log n) by bunching together repeated calculations, so if you have a million samples, that's some 70,000 times faster. At the time of its discovery it was critical for Fourier analysis to actually be reasonable to do on a computer, taking days instead of years. [0] [VIDEO] [1] [LINK] [2] [LINK]

You might also like this recent Veritasium video on the link between the Nuclear test ban treaty and FFT. [VIDEO]

Veritasium has an explainer of the Fast Fourier Transform on youtube. From how it's used and an interest history. [VIDEO]

I recommend learning about the Fourier Transform, and then peeking at how frequency transformations are used to represent everyday images, like the Cosine Transform used in JPEG. 3 blue 1 brown FFT: [LINK] JPEG components [LINK] I worked at the Very Large Array radio telescope for a while, and even so the language didn't click for me until I thought about the signal transforms that have become ubiquitous in everyday life. And a co worker described the telescope as a double-slit experiment, with multiple 2-D holes instead of slits; imagine the interference pattern that you get when you have multiple slits. The elements of an interferometer are the "slits", but they are receiving the light rather than emitting it. The VLA has 27 radio dishes for its elements, so poke 27 holes in a board and shoot a laser through the holes, you get this blurry pattern on the wall. That's the distortion from the shape of your telescope, you're trying to cancel that out... Then there's the time domain, because the Earth is rotating, so your telescope is sweeping a pattern across the sky. It can seem like a hopeless mess, but it's actually the case that for most observations, that sweep gives you even more coverage of the image. It can be a good thing. But you have to keep track of one wavefront across all of those moving elements. The correlator is a computer doing those FFTs to find where the signal matches enough between the elements to start extracting finer detail. I think some insight into ho

Consider ordinary 3 dimensional space: Go to a corner of the room, where the floor and two walls meet, and see three lines, each line the intersection of the two walls or a wall and the floor. In usual building architecture, these three lines are mutually perpendicular, i.e., orthogonal . Regard each of these three lines as an axis of a coordinate system. In particular, pick a point on each of the three axes to give us points with coordinates: (1,0,0) -- the X axis (0,1,0) -- the Y axis (0,0,1) -- the Z axis Soooo, now we have a standard coordinate system for ordinary 3 dimensional space. Now consider a point P in the room (in my case, the end of the pony tail of that sweet, gorgeous blond I keep looking at!) with coordinates (x,y,z) for some numbers x, y, z. For the X coordinate of point P we make use of the X axis and our point P: We take the dot ( inner ) product of (1,0,0) and (x,y,z) and get, presto, bingo, wonder of wonders, no doubt, x. Similarly for y and z. Or, for each axis, our inner product projects point P on that axis. And from those projections we can reconstruct the coordinates of point P. Beginning to sound like Fourier theory???? This stuff of projections onto orthogonal and then reconstructions from that generalizes. In Fourier theory, those sine waves are mutually perpendicular -- project one on another and get 0. That summation is the inner product for that projection. And if not a summation, then an integration -- same stuff, use an inner product to do p

I saw this one a while ago. [VIDEO] - The Remarkable Story Behind The Most Important Algorithm Of All Time In summary, FFT is just a "dynamic programming" version of Fourier Transforms, in that it's the same idea, just with avoiding repeating a lot of duplicated calculations.