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
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.
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 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
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 ??
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.
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.
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
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.
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
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.
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)
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)
ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-HtSuA80QTyo.html Here you go watch at 26:27 in that video, Instructor: Srini Devadas, mentions about it!
"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.
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.
So is the Nfft value for the FFT function in the matlab signal analyzer app the same as the 'n value rounded to the next largest power of 2' he talks about in the video?
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 😅
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.
actually you are wrong. It is a simple mistake n+ 2n +4n + 8n ... n*n = n( 1+ 2+ 4+ 8...n) and not n(1+2+3+4+5+6....n). Therefore, right part is not n*(n+1)/2. It is geometric series so right part is 2n-1*. Thus, it is O(n^2). * a^0 + A^1 .... a^k = a^(k+1)-1/a-1 in this case a = 2 and a^k = n.
I think there is one mistake at 15:36, when he wrote down samples to represent a polynomial of degree n. He took n samples to represent a polynomial of degree n uniquely. But this is untrue, to represent a polynomial of degree n, we need at least n+1 sample points, for all different x points.
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?
Because he's trying to invert the V-matrix which requires a complex conjugate operation and then a divide by n. Note he later corrected the division by n (because the magnitude of the xk values must be 1), and deferred it to after the matrix multiplication
