Fast Fourier Transform

In this video we show how the Discrete Fourier Transform operation can be written as a matrix operation. While this is convenient, in its native form, this is a computationally expensive operation. However, we show how the Cooley-Tukey algorithm can be used to decompose this matrix operation into a series of smaller matrix operations, thereby making it a computationally efficient and fast algorithm. This algorithm is known as the Fast Fourier Transform (FFT) and is considered to be one of the most important numerical algorithms in history. In addition the outlining the mathematical theory behind the FFT, we look at how this can be leveraged in Matlab and show a concrete example of the FFT applied to an audio frequency analysis problem.
Cooley, James W. and Tukey, John W., "An Algorithm for the Machine Calculation of Complex Fourier Series," Mathematics of Computation, Vol. 19, April 1965, pages 297-301.
Topics and timestamps:
0:00 - Introduction
3:42 - DFT in matrix form
11:57 - The FFT algorithm
30:08 - Validate matrix decomposition
41:01 - Example of FFT on audio data
All Fourier analysis videos in a single playlist ( • Fourier Analysis )
#FourierAnalysis #FourierSeries
All Matlab/Simulink videos in a single playlist ( • Working with Matlab )
#Matlab #Simulink
You can support this channel via Patreon at / christopherwlum or by clicking on the ‘Thanks’ button underneath the video. Thank you for your help!

[@ChristopherLum]

In case it is helpful, here are all my Fourier analysis videos in a single playlist kzbin.info/aero/PLxdnSsBqCrrEXKhynsK_u-suvtWzMwY5A. You can support this channel via Patreon at www.patreon.com/christopherwlum or by clicking on the 'Thanks' button underneath the video. Please let me know what you think in the comments. Thanks for watching!

[@elijahleonen198]

AE501: It was very helpful for the homework to see the MATLAB code for the FFT. Great video!

[@RajChhabraUW]

AE501: Great overview of the FFT. Definitely will help with the HW

[@tranpham7120]

AE501 I appreciate the professor for this video.

[@supmyhomi9]

AE 501: Great lecture, really appreciate the examples used and clips of Mathematica. Was definitely a huge help on the homework. Also… FIRST COMMENT. - Minja Anthony Nozinovic

[@ChristopherLum]

Nice, kudos for getting in quick and snagging the first comment :)

[@Hiyori___]

awesome lecture

[@gennionamics]

Thank you for sharing these lessons. They are very useful to catch up with topics studied in the past! Also, where do I find the video on the PSD and the video on the Fourier Transform? PS: the other spikes you see in the PSD are basically the same note but shifted octaves above. For instance in this case you will have peaks at k*256 Hz with k=1,2,.. and the highest peak correspond to the octave of the note you are playing on the instrument. There is a nice table here: en.wikipedia.org/wiki/C_(musical_note)

[@Richard_Le]

AE501 22:31 If the N was an odd number, what would the size of the N/2 matrices be?

[@ChristopherLum]

Good question, you actually can't do the FFT unless it is a power of 2. Most algorithms will actually pad your inputs until it is a power of 2.