Home Creators Posts Import Register Favorites Logout
haven't archived this post yet. have a subscription? use the importer!

Content

Hi Everyone, just a quick post here to share a lecture I did on the basics of what a Discrete Fourier Transform is for MIT's 18.S191, hope you enjoy!

At the end I reference a really excellent breakdown and motivation for the FFT algorithm by a new channel I've found which uses my animation engine, Reducible.  Here's the link: https://youtu.be/h7apO7q16V0

Files

Previews only

What is a Discrete Fourier Transform? | Week 14 | MIT 18.S191 Fall 2020 | Grant Sanderson

An overview of what Discrete Fourier Transforms do, how their defined, along with a comparison between the runtime of a naively implemented DFT and one using the Fast Fourier Transform algorithm. Video on FFT from Reducible: https://www.youtube.com/watch?v=h7apO7q16V0

Comments

Anonymous

This is great, as always! Can I ask an almost off-topic question: you mention that complex numbers come up when one thinks about walking around a unit circle. To me, having never studied complex numbers in depth, sin and cos functions are a great way to describe walking around a unit circle. I understand the relationship between complex numbers and sin/cos, but why are there these two languages? When is one better than another? Even more broadly, what do complex number give us that regular vectors and matrices do not? I’d love to further develop this on an intuitive level - I’ve seen the formulas :-). Thank you so much!

Anonymous

You mention an "epidemic section". What exactly do you mean? Could you please provide a link to this "section".

Anonymous

Yes. I don’t have any problems with e to i... my question is more about what we can do with complex numbers that we can’t do with vectors or matrices. E.g., I can describe rotations with complex numbers - but I can do the same with rotation matrices.

Anonymous

Uh oh, Grant is now of the age that he needs reading glasses. Welcome to the club!

Andrew Alvarez

I think it helps to recognize that there’s no analogue to complex number multiplication for vectors. Sure, you can construct matrix/vector products that corresponds to some complex number product, but that operation would look more convoluted and also be non-commutative. Rotational math is just way easier with complex numbers. You can represent a walk around a circle with z0 + rcos(ωt) + rsin(ωt)i (analogous to [x0 + rcos(ωt)]i + [y0 + rsin(ωt)]j for vectors) or as z0 + rexp(2πit) (no vector analogue AFAIK), and though they’re equivalent, the second form lets you compose multiple rotations way more easily. The main advantage traditional linear algebra constructs have is that they generalize to any number of dimensions, while complex numbers only work in 2 dimensions (there are “higher dimensional” complex numbers like quaternions and octonions, but those start losing algebraic properties like associativity and commutativity, because if they didn’t, they’d just reduce to complex numbers. See hypercomplex numbers for more details if you’re interested). Plus, traditional vector operations like dot products and cross products make more sense with vectors than with complex numbers.

Jeremy

Awesome content (as usual, which is why I'm a patreon of your channel). I'm a fan of the close mic, but would suggest using the high-pass filter (if there is one) to compensate for proximity effect, which will also help suppress some 1/f noise (which would be a topic I'd love to see). While you're using your mic, you might look at voice asymmetry, and phase rotation which is used on vocals in music and broadcast production to let vocals be louder without clipping - I find it very related to Fourier analysis, especially with regard to phase.