The Discrete Fourier Transform: Most Important Algorithm Ever?

Go to https://nordvpn.com/reducible to get the two year plan with an exclusive deal PLUS 1 bonus month free! It’s risk free with NordVPN’s 30 day money back guarantee!

The Discrete Fourier Transform (DFT) is one of the most essential algorithms that power modern society. In this video, we go through a discovery-oriented approach to deriving the core ideas of the DFT.

We start by defining ideal conditions and properties of our transform. We define a similarity measure and come up with an idea that the transform we are looking for is fundamentally a matrix multiplication. Within the context of simple cosine waves, we develop an initial version of our transform using cosine wave analysis frequencies that seems to fit the parameters of what we are looking for. But we discover some key issues with that transform involving the phase of the signal.

To solve the phase problem, we take a look a sine wave analysis frequencies and observe how using a combination of sine and cosine wave analysis frequencies perfectly solves the phase problem. The final step involves representing these sine and cosine wave analysis frequencies as complex exponentials. We finish the video by analyzing some interesting properties of the DFT and their implications.

Chapters:
0:00 Intro
1:50 Sampling Continuous Signals
3:41 Shannon-Nyquist Sampling Theorem
4:36 Frequency Domain Representations
5:38 Defining Ideal Behavior
6:00 Measuring SImilarity
6:57 Analysis Frequencies
8:58 Cosine Wave Analysis Frequency Transform
9:58 A Linear Algebraic Perspective
13:51 Sponsored Segment
15:20 Testing our "Fake Fourier Transform"
18:33 Phase Problems
19:18 Solving the Phase Problem
21:26 Defining the True DFT
28:21 DFT Recap/Outro

Animations created jointly by Nipun Ramakrishnan and Jesús Rascón.

References:

Great written guide on the DFT: https://brianmcfee.net/dstbook-site/c...

Proof of orthonormality of the DFT: https://math.stackexchange.com/questi...

More on the Shannon Nyquist sampling theorem: https://brianmcfee.net/dstbook-site/c...

Great intuition on the continuous Fourier Transform:    • But what is the Fourier Transform?  A...  

This video wouldn't be possible without the open source library manim created by 3blue1brown and maintained by Manim Community.
The Manim Community Developers. (2022). Manim – Mathematical Animation Framework (Version v0.11.0) [Computer software]. https://www.manim.community/

Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible

Music in this video comes from Jesús Rascón and Aaskash Gandhi

Socials:
Patreon:   / reducible  
Twitter:   / reducible20  

Big thanks to the community of Patreons that support this channel. Special thanks to the following Patreons:
Nicolas Berube
kerrytazi
Brian Cloutier
Andreas
Matt Q
Winston Durand
Adam Dřínek
Burt Humburg
Ram Kanhirotentavida
Jorge
Dan
Eugene Tulushev
Mutual Information
Sebastian Gamboa
Zac Landis
Richard Wells
Asha Ramakrishnan