26. Complex Matrices; Fast Fourier Transform
Vložit
- čas přidán 5. 05. 2009
- MIT 18.06 Linear Algebra, Spring 2005
Instructor: Gilbert Strang
View the complete course: ocw.mit.edu/18-06S05
CZcams Playlist: • MIT 18.06 Linear Algeb...
26. Complex Matrices; Fast Fourier Transform
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
MIT has done great service to mankind, by recording his lectures and sharing them online. This are so beautiful, future generations will remember him as the Mozart of this subject
not really, they are just lectures of peopole who actally understood subject and are able to communicate.
@@WojciechowskaAnnaalright anna
1.5 x Gilbert Strang = Gilbert Strong
2 x Gilbert Strang = Gilbert Stark
Binge watch = Gilbert Stretch.
3 x Gilbert Strang = Gilbert Strange--Dr. Gilbert Strange.
244u + Gilbert Strang = Gilbert Strangelove
(Gilbert Strang)^T = Gilbert Strang because he's so positive and excellent ;)
If you start your day with one of the lecture of Gilbert Strang, your day will be perfect! :-)
Yassss 😁 I feel the same 😁
Problem comes when you have to watch it twice thrice or more to fully understand it
@@cafe-tomate make a good notes from watching a lecture very slowly and go through them many times. That is how you learn math. "If you don't review your notes, you learn nothing" (a famous math guy, forget the name). Then, no need to watch lectures more than ones.
Hah! I thought it was Gilbert Strang from the Thumbnail photo 😃
@@user-pd1sx9tx4q that's cool. I do that and always watch them a second time (twice, no more) to see if I got the righr interpretation the lecturer wanted to share and I put the same idea in my notes.
This was probably the most beautiful lecture I have ever watched. The way the knowledge is passed, step after is step is pure poetry. Thank you Prof. Strang.
I envy those MIT guys who could learn from Prof.Strang in person.
Hope they could appreciate what an absolute gem of a teacher he is
17:46 "Math starts counting with one and electrical engineers start counting at zero. Actually, they're probably right."
The lecture on Complex Matrices and Fast Fourier Transform are excellent. DR. Strang also explained these two subjects in Computational Science and Engineering I and II at MIT.
Don't complain whiners. There are TWO whole courses after this one that teach JUST applied linear algebra.
1. Computational Science and Engineering I
2. Mathematical Methods for Engineers II
You can also read the book - Introduction to Linear Algebra, AND another entire book just for advanced applications - Computational Science and Engineering, both by Prof. Strang.
Ooh yes!
k
So the only background needed is this course, for the two courses you mention?
@@konstantinosarsen581 Don't forget your calculus (± DiffEq) in the meantime
Merci beaucoup
This was a real eye opener, can't thank MIT OCW enough!!
really a fantastic professor, explain all this idea so clearly and naturally. I was confused about fourier series before, now I am pretty clear!
Quality at its extreme !!! Respect professor strang !!! Hats off to you !!!
This is truly a fun series of lectures.
Amusingly, every problem seems to boil down to a problem in Linear Algebra!
What a great lecture this Professor gives... That's probably why MIT is so good, they actually hire teachers that can teach! Congratulations
So true. A professor can be a genius and a lousy teacher at the same time. Unless you’re genius yourself, you’re not gonna learn anything from such a professor.
Professor Strang is a great teacher and a genius at the same time. What a beautiful combination.
The only reason you think he's so good is because you're watching a youtube video. If you were sitting in his class you'd think he sucks. Not because he sucks but because EVERYONE thinks anyone on youtube is better than classroom professors. That's how dumb everyone is, you think youtube teachers are better than classroom teachers
@@christopherjoseph651 You are making gross assumptions on what others are thinking solely based on your own thinking about others. And you hinted that you think everyone but you is dumb.
@@christopherjoseph651 eh..OCW isn't going to pick the crappy classroom professor to distribute their content to the world!
Absolutely beautiful.. this is amazing. Thank you so much to MIT and Gilbert Strang
After a couple of years away from these topics I felt in love again with them. You gave me the light to find them again. Thanks! (there are not enough words to explain you all my gratitude about this) :-), best wishes.
Really glad I watched this to the end. I've implemented an FFT, but didn't know about the matrix factorization view of the problem.
okay this was extremely useful!
revising for exam for discrete mathematics first year at the University of Bath, and from 16:25 best way of thinking of fast fourier transforms and matrices that i have heard!! very simple, well explained, he's a great lecturer.
00:00 Complex numbers and the Fast Fourier Transform
06:33 Complex matrices have a different definition of symmetry and perpendicularity
13:07 Introduction to complex n-dimensional space and unitary matrices
19:17 Understanding the complex numbers in Fourier transform
25:08 The four by four matrix for Fourier transform is remarkable.
30:46 The columns of F4 are orthonormal, making its inverse easy to calculate.
36:15 The 64 by 64 Fourier matrix can be separated into even and odd components and then a 32 size Fourier transform can be done on them separately.
42:02 The fast Fourier transform multiplies by an n by n matrix in half n log n steps.
Crafted by Merlin AI.
Thanks Prof. Strang!!! This lecture is a work of art. I was doing some work on a DFT course and needed a comprehensive approach to DFT/IDFT, Best 50 minutes I have spent. Thanks for the tip on Hermitian and unitary matrices!!!
He is a genius...
Would be golden if the explaination to that factorization came in.
Small point: *Two* |D| size multiplies are needed so in a few places where he says 32 it should be 2*32.
Thanks, merci beaucoup prof Strang, absolute brillant
What an amazing lecture, thank you!
Thanks Gilbert...love your work. JS
This is my favorite lecture
Prof Strang is the best “old school” teacher you can imagine. Black board and chalk, straightforward and to the point. And no fancy techtronics
Old is gold
00:00 Hermitian Matrices
16:34 Fourier
I watched the second video of 6.046J (Design and Analysis of Algorithms), and Erik Demaine explained FFT. That video confused me so fast so much, that I decided to watch18.01, 18.02, and 18.06. Looks like I was right in guessing that this course should be a prereq for 6.046J (even though it isn't).
Happy to see FFT in a pure Linear Algebra context :D
At the end I remembered I never read about fourier transform only fourier series. Thought I was going insane for a second.
simple yet elegant; erudite yet conveyable
The conjugate transpose is written with H for Hermitian. In quantum mechanics, we use the "dagger" symbol which looks like a cross.
I took a math class in harmonic analysis and we used star for it. 😊😊
girlbert is my homie
Ty for uploader
25:46 Strang: "I squared I cubed... I squared I cubed... "
Me: "You sure did :DDD"
Thing that he said eventually is so nice for the computer engineers to understand how computational circuits uses FFT in order to increase efficiency 🥰🥰🥰 legend Gilbert
being confused for more than 20mins with FFT, still watched the whole lecture oops haha, omgg, good jobbbbbbbbbb!
I can't continue the course anymore, the last 30 minutes of this lecture seems to be way too much for me. *after trying to understand the first 15 minutes of his last 30 minutes for an hour and I'm still confused.
Appreciate your work Professor Strang. It's a great experience learning from you.
Got this lecture bookmarked, I'll return to it one day
Not sure how's your relation with LA, but - coming from this no hard-science-back-grounded-guy here - you might check 3Blue 1Brown Euler's coeficient videos. I have been following both courses simultaneously and that gave me a good clue to get along with this lecture. Best of luck!
also 3b1b lockdown math course.
@@jefthervieira1 I see you are a man of culture.
Be sure to use the regular transpose (not the Hermetian transpose) when calculating the inverse of a complex matrix from the cofactor matrix. I found out the hard way Matlab and Octave's transpose operator ( ' ) will do the Hermetian transpose. If you want the regular old transpose, you have to use the transpose() function explicitly.
This lecture was made just fine for dft.
He's talking about multiplying a matrix by a vector, which is O(n^2).
I am a computer science undergrad watching these lectures because I felt I needed to understand Linear Algebra better for two fields: Machine Learning and Quantum Information. It's incredible that both of these get some overlap with this linear algebra course (ML was touched on when we did projection matrices as that is exactly the closed form solution to linear regression), and now QI which uses Complex vectors spaces is being covered.
:)
And the Fourier Matrix is the QFT !
at 31.20 when making the columns orthonormal by dividing by 1/2 , F4 should also be divided and the new matrix 1/2(F4) is orthornormal. Then the new matrix and its hermitian are equal to the Identity, which means F4^H x F4 = 4I. Right?
Gotta respect Gilbert Strang.
This lecture made so much sense. My current professor doesn't do a good job in keeping it interesting. Great lecture!
I think prof. Strang gave a much better explanation of the FFT algorithm in his other course - Mathematical methods for engineeers I
(1)Does it matter which matrix is taken the conjugate of when computing the standard norm?
No students today :{
I just messed up in the odd odd, odd even part, whatever the rest is wonderful. Thanks to Prof. Strang from India.
Cutest teacher! EE starts counting from 0, we start counting from 1. Actually they probably right.
Great video to watch after watching many quantum computing videos and realized you missed a class back to your university times 🤣🤣
Good time!
Genius!
@l955382 it's like an identity matrix except the 1s don't go across the diagonal. The 1s are moved here and there to denote row operations
Why do we do permutations of 32-matrix?
I dropped out of electrical engineering degree, and here it is, following me around with no chill. Maybe this is a sign lol
So what did you major in?
So you switched from 0-based to 1-based world.
@@rosadovelascojosuedavid1894 I dropped out of college. I never graduated. Turns out I’m a pretty lousy student lol. If I knew then what I knew now, I would have double majored in computational math and applied physics with a minor in computer science.
@@nenadilic9486 lol for a time. But the 0-based world pulled me right back haha 😅
@@ozzyfromspace Now you're a J-man instead of I-man ;)
Is there a playlist where all of these lectures on Linear Algebra of 18.06 can be accessed?
For every course taught by Professor Strang?
Here's the playlist for 18.06SC: czcams.com/play/PL221E2BBF13BECF6C.html. You can find the course materials on MIT OpenCourseWare at: ocw.mit.edu/18-06SCF11. Best wishes on your studies!
He made a pretty good circle with one quick move xD
40:03 why the fixed count part is 32? I thought 64 since we have 2 D in the left matrix.
As you can see it is D and -D that will both multiply F_32. Do Basically, the result will be DF_32 and -(DF_32). Reversing the sign can be done for "free" (compared to a multiplication) so there is only DF_32 to compute, hence cost 32. Anyway this is just an illustration and complexity analysis shouldn't account for constant factors: in the end, the number of operation is linear in n, that's all that count.
The mathematics of Quantum Mechanics!
The difference between EE and Math dept is EE starts counting at 0 and Math at 1....paraphrased at 18:10. That made me laugh.
In other places, the DFT matrix has a minus in the exponential (en.wikipedia.org/wiki/DFT_matrix). What am I missing here?
In that Wikipedia article they say "a clockwise DFT matrix". What he showed would be the counterclockwise (the same direction in which angles are measured in math). Anyway , the two matrices are the same except the signs of i are the opposite, due to this reflection around the real axis, and so one is the Hermitian of the other. When one is a transform of a function, the other one is a reverse transform. A reverse transform is nothing but the Fourier transform of another function, the one that itself is a Fourier transform of the original function... or the direct transform if you start in that other domain.
@38:45 why did we count the fix-up cost from just one of the D's. Shouldn't it be twice since we have D and -D in the matrix?
Think what's -D compared to D? :D
For the FFT, there's another truth to be noticed. $$w_{64}^k = -1.0 * w_{64}^{k+32}$$ Also for this reason, -D appears here.
I am shocked at 40:48, why isn't there any students at the lecture hall?
Isn't the order of complexity for multiplication b/w 2 n x n matrices O(n^3) and not O(n^2)?
Correct, but here we are talking about multiplying an nxn matrix with a vector. Each function is a vector with infinite number of coordinates, but when we discretise it (sample it), we get a n-dimensional vector. A matrix linearly transforms a vector by multiplying it on the left, and the Fourier matrix transforms a function in the same way.
i lost my mind when he taught about FFT. Anyway, Prof Gil. Strang is brilliant.
I lost it at the end... That is soooo confusing!
32:41 - that's where the FFT part starts.
Am I only one realize that there is nobody in class?
wish i could be the audience
No sometimes Gilbert strang records his lectures alone for Courseware
Duh corona time remember?
I have lost myself for the last 10 minutes lol
37minute i dont understand please supplementary data ㅜ
what even is a fourier transform?
Look at MIT 18.03 lectures 15-17.
@44:25 2 (2 (2 (2 (2 (2 + 1) + 2) + 4) + 8) + 16) + 32 = 256 ， not 6×32 = 192
2 (2 (2 (2 (2+2) +4) +8) +16) + 32=192=6*32
@@lsun9593 i didn't get you, could you clarify?
i think it should be n + n/2 log n
Maybe a year too late, but if someone else reads this, I get an additive n rather than n/2 term, too. I think the fact that there are 2 diagonal W matrices of order n/2 was a mistake but he did an excellent job presenting this material. I think it's a mistake based on what I understand, but an inconsequential mistake when considering computational complexity.
@@joem8251 Impossible to comment without seeing the work, but focus on D's; we only need to compute them once (-D need NOT be computed as it is a sign change). Each factorization doubles the number of D's but reduces the elements in D's by half as well, thereby keeping the number of multiplications constant on each step which is (1/2)*n
32:56
i will tell you why u understand everthing here..This professor is great and the other thing is..This lecture wont be explained in 10 minutes like here in Germany. Of course u understand fucking nothing if you explain such important things in 10 minutes and then begin with new stuff.
Hi, does the i in this video stand for imaginary number or i hat ?
at 26:42
sqrt (-1)
I am controlled by the combination of FFT and linear algebra....
Fast fourier transform part was too tough for me
Near 23 min in, how did he ignore the i, but remember it in his next example with n = 4?
Not sure what you're talking about. He said "i" everywhere it needed to be said, and wrote "i" everywhere it needed to be written.
conjugate
All his application lectures seem kind of sloppy
There are two other courses focusing on applications that he teaches (both were made open source). This is a basic course which should only show initial connection between the fundamentals and applications.
LOL numbers are just ideas.So technically I can't be wrong l.O l
He's just showing applications of linear algebra, not teaching them. That's why it seems "sloppy". You just can't teach Fourier Transform in 30 mins.
He doesn't have to teach Fourier in 30 mins. These students have already had 18.03. Look at Prof. Mattuck's lectures 15-17.
There are two other courses focusing on applications that he teaches. This is a basic course which should only show initial connection between the fundamentals and applications.
Lecture 26 is Professor Strang’s best performance so far.
In lecture 25, in front of students, he screwed up his proof showing real symmetric matrices have real eigenvalues. Got confused and had to refer to his notes. In this lecture, in front of no students, he gives a tour de force performance.
Hope there no students in his remaining lectures, because his cyberspace audience is orders of magnitude larger than his MIT audience.
I loved the way how he smoothly recovered the proof consulting his notes, I would be lost just staring at the notes not even seeing anything. He found why he didn't finish the proof the first time around and explained the reason to students (and us) and what was the main reasoning behind the proof, so not did I only learn the matter but also learned how to make proofs myself and what to do when I reach the dead-end like 0 =0 or 1 = 1.
Of course to be a real Electrical Engineer you should use j for imaginary numbers.
Use a hat or a bag
this is the least satisfying of the Strang lectures I've seen. everything is so dumbed down until he gets into factoring the Fourier matrix and then all of the sudden doesn't really show that the factorization is correct. Not even a rudimentary hand-waving.
Perhaps the students could check that it is correct themselves? Given
that there is so much structure here, it is quite easy to check. He suggests as much at 39:59.
Furthermore, his book has the algebra on pages 512-513. We must
remember that these lectures are not meant to instruct outsiders from
scratch. They are merely a window into the MIT experience, which
includes, as all good programs of study do, an expectation that students
read the book, attend recitations, and do some work on their own. The
reading of books (or the internet) and doing work on their own is the
most critical part, as this is the only way they will learn once they
are out of school. Anyone watching these videos should be expected to
do the same.
what the hell bro.. study complex nums and cube roots or nth roots of unity then you'll get it. At least don't blame the prof. for your past ignorance.