Just a tip for new viewers: Don't stop!! Continue watching the video, don't expect yourself to understand everything as you go, grab the essence of each section of the video and in the end it is all gonna make sense. If it did not you can always go back but don't quit this video. Amazing job Erik!!!
Thank youu, I rewatched 3 times before i actually got it. And I think i will rewatch for the 4th time to understand more on execution time complexity and some concepts which were mentioned but not explained enough
This is the best explanation of the FFT you can find very intuitive and step by step. Most people explain the FFT with a matrix of coefficients and I just never understood it until I saw this more algorithm oriented explanation
I first encountered the FFT derivation of the DFT thirty years ago when I took a digital filters class while a graduate student at Georgia Tech, and I am as bolled-over now as I was then by this most elegant and incredibly useful algorithm. Thank you, Professor Demaine. --
The part about how size of X needs to be reduced by 2 when we go to X^2 is just brilliant! That explains the choice of x_k's that I saw on other ppl's implementation so well!
It's called railroad chalk. Made with calcium sulfate (gypsum), not calcium carbonate (chalk). Softer than chalk hence bolder lines and no screech. Dustier though, so treated with a dust inhibitor, that's why the surface of the stick is yellow but it writes in white.
Me: Has a school assignment where I have to implements an algorithm dividing two polynomials and I have no idea what to do This man: I'm about to save this man whole career
Having barely mastered some basic arithmetic, this may be a little advanced...even though I have no idea wtf this guy is talking about/drawing, it is fascinating to try and understand it.
is there a mistake @28:35 ? we know V.A = Y ( V - vandermond matrix, A - coefficien matrix, Y - samples matrix) (multiplying by V inverse i.e. V^(-1) both sides) => V^(-1).V.A = V^(-1).Y => A = V^(-1).Y So to go from samples matrix to coefficient matrix we need to do V^(-1).Y right ??
The root representation should be (x-r1)...(x-r(n-1)) not from (x-r0), you can easily see that if you do it from r0, then you will have polynomial of x^n (which is one degree higher than what he used in the first rep.)
He did this because he claimed you need n points to represent an n-1 polynomial. If you watch later into the video, he wrote it in this weird way cuz he was centring things around the number of points you need, not the number of coefficients represent the polynomial.
COOL! The only thing I don't prefer ( for lack of nicer word ) is the fact that he used a claim for last proof (IFFT). The problem with claims is that they are the result of some careful thinking, we're just proving that that thinking is correct. It would have been beautiful if he showed us the steps that resulted in the inverse of V being a n * V conjugate so we can fully sympathize for I believe sympathizing is the best way to learn math
"Screw Pi" - omg i nearly died. That was hilarious. I deeply regret my decision to avoid STEM classes in high school and college. That was a terrible mistake.
It’s not too late to learn. Think of the ones you regret not taking and either purchase a book or take a class. One of the greatest things about our minds is that they are malleable.
I was just thinking earlier today about root 2/2 being the sine and cosine of 45 degrees, e^(2)i pi (e^i tau) and how they related to the unit square and circle. Fourier, Gauss, Dirichlet all stood on Euler's shoulders.
Okay, we've figured out how to convert between different representations of polynomials, but how do we go from there to the familiar application of the FFT - converting between the time domain and frequency domain? Given a bunch of samples, we want a weighted sum of sinusoids, but what we get here is the coefficients of a polynomial.
@@sophiophilethe coefficients that we get IS the FT, instead of the points being the coefficients of the polynomial representing the time domain function we get the samples from the polynomial representing the polynomial in frequency domain.
I guess the idea is to somehow encourage participation. I'd like to know if there's a more in-depth study about this - does it enhance or take away concentration from the actual subject? (Or choice C - neither, it's just a bit of fun)
the product of two n-1 degree polynomial will be 2n-2 and we need 2n-1 unique points to derive a 2n-2 degree polynomial and nth root of 1 gives just n points and not 2n So My question is dont we need 2n points intead of n?
It's already been noted that two polynomials should be reduced to the same degree and up to the nearest power of 2 (simply by adding the coefficients with zeros). In addition, as a result of the product of two polynomials of degree (n - 1) a polynomial of degree (2n - 2) is obtained; therefore, in order for the result to be correct, it is necessary to double the degrees of each polynomial (again by adding zero coefficients to them)
around 1:20:00, you can't get pure sine wave from striking a bell. Bell, or piano, or a person singing the same note each has a unique timbre to it. Use an online sine wave generator and listen to what a pure tone sounds like (at a certain frequency). Sing that out feel the difference, and view it under a frequency analyzer, they will look vastly different.
Did I come here planning to learn about the nth roots of unity and how polynomial representations can be exploited to improve the scaling of computational complexity... No Did I just spend an hour watching this guy because it is freaking interesting and incredibly well presented? You bet I did 😅
What does A(x), B(x) and C(x) indicate here for computing FFT? ig A(x) is some discrete input 1, B(x) is some discrete input 2 which is impulse response function of the system and C(x) is the discrete time output. am I correct?
Squaring those numbers will give you 1, 1, 4, 4, giving you the set {1, 4} (a collapse of 4 numbers to 2), but if you square those again you get {1, 16}, which doesn't collapse the set any further. You need the collapsed set to collapse again when you square each value a second time, and then collapse again when you square the numbers a third time, and so on, hence the complex numbers. You could use the nth roots of any number, but using the nth roots of 1 is simpler and lends the alternative representation to represent amplitude and phase information in frequency space. If you used the nth roots of another number I don’t think the alternative representation could be interpreted the same way.
@@elliotwaite 1:07:35 if the complex conjugate is just minus the power in the exponential, why did he write exp(-ijkT/n/n)? why the divide by n divide by n (again)? is it a mistake? (also sorry I asked as subcomment; I thought it'd get lost in the clutter otherwise)
@@haardshah1676 it looks like the second division by n was a mistake. He realizes this soon after writing it and erases it. Does that answer your question?
How does one perform FFT on a larger domain consisting of multiple cosets of a multiplicative subgroup of the field? I've heard it can be done but couldn't find any sources that explained how.
At 1:05:00, should not the size of the sample vector $C^*$ of $C$ be larger than that of $A$ and $B$, given that the polynomial $a*b$ has degree $2n$ if $a$ and $b$ have degree $n$?
So what is the math doing in practical terms? If I understand correctly, it's using the behavior of a signal over time to determine specific properties of that signal at specific moments. Is that correct?
The FFT has a lot of applications. What it's most usually associated with is frequency decomposition. The FFT is just a computationally faster way to calculate the discrete Fourier transform of a periodic signal, which extracts the frequency components of a signal. This is used for basically everything that deals with periodic signals. More generally, the FFT can be expanded to include different roots of unity, like finite fields or integer integer rings, and that is used for cryptography and other various topics. As far as practicality, this algorithm is a major step forward in the advancement of our species. It touches nearly everything in our current world.
Just a tip for new viewers:
Don't stop!! Continue watching the video, don't expect yourself to understand everything as you go, grab the essence of each section of the video and in the end it is all gonna make sense. If it did not you can always go back but don't quit this video. Amazing job Erik!!!
Thank you
This is very wise advise.
Thank you
I followed the strategy and now reading this comment. Going to advise the same
Thank youu, I rewatched 3 times before i actually got it. And I think i will rewatch for the 4th time to understand more on execution time complexity and some concepts which were mentioned but not explained enough
This is the best explanation of the FFT you can find very intuitive and step by step. Most people explain the FFT with a matrix of coefficients and I just never understood it until I saw this more algorithm oriented explanation
Erik: "I didn't go to high school but I assume in high school you learned this..."
Students:"hahahaha"
convolution: 12:46
@@julius333333 and yet he’s such a humbling, sympathetic person
8:56
Weird flex but it hurts
I first encountered the FFT derivation of the DFT thirty years ago when I took a digital filters class while a graduate student at Georgia Tech, and I am as bolled-over now as I was then by this most elegant and incredibly useful algorithm. Thank you, Professor Demaine.
--
This is the best overview of what FFT is, brilliant teacher!
The part about how size of X needs to be reduced by 2 when we go to X^2 is just brilliant! That explains the choice of x_k's that I saw on other ppl's implementation so well!
Amazing to see that such a brilliant guy can also be a brilliant educator. From my experience this is pretty rare!
Am I the only one really impressed by the quality of that chalk? It never makes those high pitched sounds ... soo smooth
It's called railroad chalk. Made with calcium sulfate (gypsum), not calcium carbonate (chalk). Softer than chalk hence bolder lines and no screech. Dustier though, so treated with a dust inhibitor, that's why the surface of the stick is yellow but it writes in white.
I didnt want to watch this video because i hate that sound so much, thank you for the reassurance so i can watch without fear
Is it hagoromo?
@@vishalvibes_ nope
Professor makes his lecture seems the learning material is so easy! Thank you!
This is THE BEST FFT lecture ever. Erik is simply awesome!
Not going to lie, I cam here to learn the FFT as an engineering student, but stuck around to learn about this CS time complexity.
same here haha
Kinda the whole point of the fft
These tattoo jokes tho. BRILLIANT!
As he puts it, this all was "very cool, very cool".
Thanks, Erik.
27:46, we can use Lagrange's Formula to compute Coefficients from Samples. It is O(n^2) but avoids inverse computation by Gaussian Elimination.
Its always a pleasure to listen Eric's lecture. Great professor.
Didn't know that Jin from SamuraI Champloo now teaches at MIT.
Thanks for the amazing overview of FFT. Amazing lecture
lmaooo did not expect to see a samurai champloo reference while learning about the FFT
Throughout the whole video i could not stop wondering about him(he is a child prodigy, became a professor at MIT at 20 )
This guy oozes brilliance! Amazing lecture!
This is the most beautiful algorithm I have seen
One of the best lectures I've seen :) really brings out the true nature of the DFT
Real men cried at the end when he brought up those applications. Truly beautiful mathematics
Gave an in depth understanding of FFT...Brilliant Explanation
I don't know how I used to call myself an engineer before watching this video!
Erik: "I didn't go to high school but I assume in high school you learned this..." reminds me seldon cooper
My Brain Stack starts overflowing after 35:00.
Beware of the plot τwist.
Hidden spoilers
Me: Has a school assignment where I have to implements an algorithm dividing two polynomials and I have no idea what to do
This man: I'm about to save this man whole career
Modify euclidean algorithm for gcd
this lecture is freaking amazing
Having barely mastered some basic arithmetic, this may be a little advanced...even though I have no idea wtf this guy is talking about/drawing, it is fascinating to try and understand it.
@@aristosgeorgiou6060 yeah, very relatable, lol
@@aristosgeorgiou6060 lol 🤣
@@aristosgeorgiou6060lol😂
Implemented FFT algo for both polynomial multiplication and integer multiplication
Deadly algo :)
% java FFTPolynomialMultiplication
i/p polynomial A :
2 + 3x + xˆ2
i/p polynomial B :
1 + 2xˆ2
n (=2ˆk) = 8
o/p polynomial C :
2 + 3x + 5xˆ2 + 6xˆ3 + 2xˆ4
% java FFTPolynomialMultiplication
i/p polynomial A :
8 + 7xˆ2 + 3xˆ3 + 9xˆ5
i/p polynomial B :
4 + 5x + 6xˆ2 + 7xˆ3 + 8xˆ4
n (=2ˆk) = 16
o/p polynomial C :
32 + 40x + 76xˆ2 + 103xˆ3 + 121xˆ4 + 103xˆ5 + 122xˆ6 + 78xˆ7 + 63xˆ8 + 72xˆ9
% java FFTIntegerMultiplication
i/p integers :
A = 123,456,789
B = 956,227,496
n = 32
product = 118,052,776,209,670,344
% java FFTIntegerMultiplication
i/p integers :
A = 2,147,483,647
B = 2,147,483,647
n = 32
product = 4,611,686,014,132,420,609
how to be a frisbee player
join as MIT lecturer
*Stands up & claps* Eric, take a bow. This should be the reference for any instructor of how to explain the FFT.
High pass filter removes low frequency, and low pass filter removes high frequency
yeah, I caught this as well.
Erik is Demaine man!
The tatoo gag is amazing!
is there a mistake @28:35 ?
we know V.A = Y ( V - vandermond matrix, A - coefficien matrix, Y - samples matrix)
(multiplying by V inverse i.e. V^(-1) both sides)
=> V^(-1).V.A = V^(-1).Y
=> A = V^(-1).Y
So to go from samples matrix to coefficient matrix we need to do V^(-1).Y right ??
you are right.
it is a mistake
I think you are correct
Yes, this should be V^{-1} Y
This is what reaching GOD Level feels like in teaching?
if there is a god, MIT is doing her work
i was present in this class
That's a great thing. What are you doing now brother...?
Wow you went to mit? How did you apply, from India or USA?
Erik: " I didn't go to high school, but I assume in high school algebra you learn this...."
Me: Drop from CS and cry...
Phenomenal lecture.
The root representation should be (x-r1)...(x-r(n-1)) not from (x-r0), you can easily see that if you do it from r0, then you will have polynomial of x^n (which is one degree higher than what he used in the first rep.)
He did this because he claimed you need n points to represent an n-1 polynomial. If you watch later into the video, he wrote it in this weird way cuz he was centring things around the number of points you need, not the number of coefficients represent the polynomial.
COOL! The only thing I don't prefer ( for lack of nicer word ) is the fact that he used a claim for last proof (IFFT). The problem with claims is that they are the result of some careful thinking, we're just proving that that thinking is correct. It would have been beautiful if he showed us the steps that resulted in the inverse of V being a n * V conjugate so we can fully sympathize for I believe sympathizing is the best way to learn math
This guy is so cool
Excellent explanation.
at last, absolute detail!
wonderful teacher
This guy is amazing
"Screw Pi" - omg i nearly died. That was hilarious. I deeply regret my decision to avoid STEM classes in high school and college. That was a terrible mistake.
It’s not too late to learn. Think of the ones you regret not taking and either purchase a book or take a class. One of the greatest things about our minds is that they are malleable.
Brilliant teacher!
I was just thinking earlier today about root 2/2 being the sine and cosine of 45 degrees, e^(2)i pi (e^i tau) and how they related to the unit square and circle. Fourier, Gauss, Dirichlet all stood on Euler's shoulders.
it always comes back to euler like it's rome
all roads, somewhere, somehow, all lead to euler
Okay, we've figured out how to convert between different representations of polynomials, but how do we go from there to the familiar application of the FFT - converting between the time domain and frequency domain? Given a bunch of samples, we want a weighted sum of sinusoids, but what we get here is the coefficients of a polynomial.
This question has been plaguing me for a while. Did you ever discover an answer to this.
@@sophiophilethe coefficients that we get IS the FT, instead of the points being the coefficients of the polynomial representing the time domain function we get the samples from the polynomial representing the polynomial in frequency domain.
Did he just throw a Frisbee at 4:54 ? I cracked up xD
I guess the idea is to somehow encourage participation. I'd like to know if there's a more in-depth study about this - does it enhance or take away concentration from the actual subject? (Or choice C - neither, it's just a bit of fun)
let me know if u ever found an answer to it @orbik.
sounds a little like dog training where you throw a frisbee as a reward for the dog.
ua-cam.com/video/HtSuA80QTyo/v-deo.html Here you go watch at 26:27 in that video, Instructor: Srini Devadas, mentions about it!
Nice lecture! I thought MIT classes would be very hard.
MIT isn't a place for geniuses, it's just a normal university that only accepts students that can apply themselves.
This was AWESOME! Thank you!
I'm in third semester,but this particular video seems to much difficult ,there are so many things in this I don't know
the product of two n-1 degree polynomial will be 2n-2 and we need 2n-1 unique points to derive a 2n-2 degree polynomial and nth root of 1 gives just n points and not 2n So My question is dont we need 2n points intead of n?
It's already been noted that two polynomials should be reduced to the same degree and up to the nearest power of 2 (simply by adding the coefficients with zeros). In addition, as a result of the product of two polynomials of degree (n - 1) a polynomial of degree (2n - 2) is obtained; therefore, in order for the result to be correct, it is necessary to double the degrees of each polynomial (again by adding zero coefficients to them)
around 1:20:00, you can't get pure sine wave from striking a bell. Bell, or piano, or a person singing the same note each has a unique timbre to it. Use an online sine wave generator and listen to what a pure tone sounds like (at a certain frequency). Sing that out feel the difference, and view it under a frequency analyzer, they will look vastly different.
53:06, 57:15 takes a moment to give tau some respect. Big flex 💪
Did I come here planning to learn about the nth roots of unity and how polynomial representations can be exploited to improve the scaling of computational complexity... No
Did I just spend an hour watching this guy because it is freaking interesting and incredibly well presented? You bet I did 😅
This was hard. Hope i will understand it soon.
LOL 53:04 ^ 57:15 ^ 1:17:08
What does A(x), B(x) and C(x) indicate here for computing FFT? ig A(x) is some discrete input 1, B(x) is some discrete input 2 which is impulse response function of the system and C(x) is the discrete time output. am I correct?
53:07 "I believe in Tau so much, I got it tattooed on my arm..."
wow,lollllllllllll
is it just me or does he look like post malone had a studious brother
Nicely explained
44:00 in this moment, all the other stuff about fft made a little more sense :-)
Sir what is the best programming language for analysis and design of data structures and algorithms??...
in 42:06 I think we need to compute the sum of cost in each level not only the last !!!
I like this guy
Great Job!
I love you teacher
FFT sounds like fast Fourier transformation I don’t know what it is though
I loved this video.
Let me guess, it involves powers of 2?
TAU IS A WHOLE CIRCLE
Amazing!
Best lecture
Dude. I admire your hair. I'm jealous. All my hair is falling out. I'll be bald soon.
I think he meant V\Y not V\A at around 29:00...
i think so too
OMG why is this not the standard way of introducing FFT
Marvellous
holy crap, the tau thing
"I didn't go to high school but I assume in high school you learned this"
you dont have to flex like eric :(
Why do we still have x elements when we split the set and each part has n/2? I'm a bit confused on this part any help would be appreciated. Thanks.
why we must take the nth root of unity, cant we take like -1, 1, -2, 2 ....as X? This will also collapse?
Squaring those numbers will give you 1, 1, 4, 4, giving you the set {1, 4} (a collapse of 4 numbers to 2), but if you square those again you get {1, 16}, which doesn't collapse the set any further. You need the collapsed set to collapse again when you square each value a second time, and then collapse again when you square the numbers a third time, and so on, hence the complex numbers. You could use the nth roots of any number, but using the nth roots of 1 is simpler and lends the alternative representation to represent amplitude and phase information in frequency space. If you used the nth roots of another number I don’t think the alternative representation could be interpreted the same way.
@@elliotwaite 1:07:35 if the complex conjugate is just minus the power in the exponential, why did he write exp(-ijkT/n/n)? why the divide by n divide by n (again)? is it a mistake?
(also sorry I asked as subcomment; I thought it'd get lost in the clutter otherwise)
@@haardshah1676 it looks like the second division by n was a mistake. He realizes this soon after writing it and erases it. Does that answer your question?
How does one perform FFT on a larger domain consisting of multiple cosets of a multiplicative subgroup of the field? I've heard it can be done but couldn't find any sources that explained how.
Awesome!
Dude, why are you erasing the chalkboard before I finish taking notes?
At 1:05:00, should not the size of the sample vector $C^*$ of $C$ be larger than that of $A$ and $B$,
given that the polynomial $a*b$ has degree $2n$ if $a$ and $b$ have degree $n$?
It's unfortunate that there's no discrete examples.
Problem sets with solutions (and other materials) are available on MIT OpenCourseWare at: ocw.mit.edu/6-046JS15. Best wishes on your studies!
💥 when Marty McFly arrives in 1965 💥
Erik, the best
His sentient, verbal expression of tau is more eloquent than a tattoo could ever be. Eloquence is human, expression is animal, marks are for objects.
That's a really pretentious way to voice the opinion you don't like tattoos, but okay lil bro
I love how he advocates for tau with so much passion he got a tattoo!
And yes I support tau!
Well... a "tattoo" using a laser-jet printer and a temporary tattoo kit.
love it!!
Pro Erik is fabulous
So what is the math doing in practical terms? If I understand correctly, it's using the behavior of a signal over time to determine specific properties of that signal at specific moments. Is that correct?
The FFT has a lot of applications. What it's most usually associated with is frequency decomposition. The FFT is just a computationally faster way to calculate the discrete Fourier transform of a periodic signal, which extracts the frequency components of a signal. This is used for basically everything that deals with periodic signals.
More generally, the FFT can be expanded to include different roots of unity, like finite fields or integer integer rings, and that is used for cryptography and other various topics.
As far as practicality, this algorithm is a major step forward in the advancement of our species. It touches nearly everything in our current world.
Does anyone have intuition as to why Fourier transforms pop up here?
whats the deal with those frizbees?