title
The Discrete Fourier Transform (DFT)

description
This video introduces the Discrete Fourier Transform (DFT), which is how to numerically compute the Fourier Transform on a computer. The DFT, along with its fast FFT implementation, is one of the most important algorithms of all time. Book Website: http://databookuw.com Book PDF: http://databookuw.com/databook.pdf These lectures follow Chapter 2 from: "Data-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Control" by Brunton and Kutz Amazon: https://www.amazon.com/Data-Driven-Science-Engineering-Learning-Dynamical/dp/1108422098/ Brunton Website: eigensteve.com

detail
{'title': 'The Discrete Fourier Transform (DFT)', 'heatmap': [{'end': 346.247, 'start': 312.884, 'weight': 0.737}, {'end': 394.922, 'start': 379.877, 'weight': 0.738}, {'end': 592.429, 'start': 545.741, 'weight': 0.92}, {'end': 825.066, 'start': 800.996, 'weight': 0.862}, {'end': 1002.45, 'start': 969.817, 'weight': 0.783}], 'summary': 'Explores the significance and practical applications of the discrete fourier transform (dft) in various fields such as image compression, audio signal analysis, diagnosing car issues, and computational efficiency, leading to the powerful fast fourier transform (fft) algorithm.', 'chapters': [{'end': 125.159, 'segs': [{'end': 125.159, 'src': 'embed', 'start': 76.126, 'weight': 0, 'content': [{'end': 83.272, 'text': "It's used for image compression, audio compression, signal processing, high performance scientific computing, you name it.", 'start': 76.126, 'duration': 7.146}, {'end': 88.496, 'text': 'Fast Fourier transform is probably at the heart of some of these computations.', 'start': 83.852, 'duration': 4.644}, {'end': 99.579, 'text': 'And what I want to get across right now is that the discrete Fourier transform is a mathematical transformation that can be written in terms of a big matrix multiplication.', 'start': 89.577, 'duration': 10.002}, {'end': 108.721, 'text': 'The fast Fourier transform is a computationally efficient way of computing the DFT that scales to very, very large data sets.', 'start': 100.54, 'duration': 8.181}, {'end': 111.462, 'text': 'So in some sense these are kind of synonymous.', 'start': 109.362, 'duration': 2.1}, {'end': 114.883, 'text': 'The FFT is how we compute the DFT.', 'start': 111.842, 'duration': 3.041}, {'end': 119.875, 'text': "But today I'm going to tell you about the DFT, the discrete Fourier transform,", 'start': 116.512, 'duration': 3.363}, {'end': 125.159, 'text': "and soon I'll show you how to actually numerically implement this via the FFT.", 'start': 119.875, 'duration': 5.284}], 'summary': 'Fast fourier transform is used for various computations, including signal processing, and is a computationally efficient way of computing the dft.', 'duration': 49.033, 'max_score': 76.126, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nl9TZanwbBk/pics/nl9TZanwbBk76126.jpg'}], 'start': 6.8, 'title': 'Discrete fourier transform', 'summary': 'Discusses the significance of the discrete fourier transform in applications like image compression, audio compression, and signal processing, leading to the fast fourier transform (fft), a powerful computing algorithm.', 'chapters': [{'end': 125.159, 'start': 6.8, 'title': 'Discrete fourier transform', 'summary': 'Discusses the importance of the discrete fourier transform, which is used in various applications such as image compression, audio compression, and signal processing, and eventually leads to the fast fourier transform (fft), one of the most powerful algorithms in computing history.', 'duration': 118.359, 'highlights': ['The fast Fourier transform (FFT) is one of the most important algorithms today, used for image compression, audio compression, signal processing, and high performance scientific computing.', 'The discrete Fourier transform (DFT) is a mathematical transformation that can be written in terms of a big matrix multiplication.', 'The DFT is an extremely important concept and is eventually used to compute the FFT, which scales to very large data sets and is a computationally efficient way of computing the DFT.']}], 'duration': 118.359, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nl9TZanwbBk/pics/nl9TZanwbBk6800.jpg', 'highlights': ['The fast Fourier transform (FFT) is one of the most important algorithms today, used for image compression, audio compression, signal processing, and high performance scientific computing.', 'The DFT is an extremely important concept and is eventually used to compute the FFT, which scales to very large data sets and is a computationally efficient way of computing the DFT.', 'The discrete Fourier transform (DFT) is a mathematical transformation that can be written in terms of a big matrix multiplication.']}, {'end': 545.741, 'segs': [{'end': 256.964, 'src': 'embed', 'start': 212.874, 'weight': 0, 'content': [{'end': 220.277, 'text': 'You can figure out if this is audio data, you can figure out what are kind of the tones that add up to make that audio data.', 'start': 212.874, 'duration': 7.403}, {'end': 224.459, 'text': 'I always tell my students, you know, what I want to do is build an iPhone app.', 'start': 220.297, 'duration': 4.162}, {'end': 230.361, 'text': 'So you put it on the roof of your car or the hood of your car, and it listens to the audio signal.', 'start': 224.479, 'duration': 5.882}, {'end': 231.962, 'text': 'It computes a Fourier transform.', 'start': 230.401, 'duration': 1.561}, {'end': 236.964, 'text': "And based on the frequency content, maybe it can diagnose if something's wrong with your car.", 'start': 232.482, 'duration': 4.482}, {'end': 240.306, 'text': "like you have a belt slipping or some kind of vibration that shouldn't be there.", 'start': 236.964, 'duration': 3.342}, {'end': 250.197, 'text': 'OK, so turning a data vector into its sine and cosine components through this discrete Fourier transform can be very, very useful.', 'start': 240.886, 'duration': 9.311}, {'end': 256.964, 'text': "It's also nice to compute derivatives, to approximate derivatives of data.", 'start': 250.938, 'duration': 6.026}], 'summary': 'Using fourier transform to diagnose car issues from audio data.', 'duration': 44.09, 'max_score': 212.874, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nl9TZanwbBk/pics/nl9TZanwbBk212874.jpg'}, {'end': 346.247, 'src': 'heatmap', 'start': 281.914, 'weight': 2, 'content': [{'end': 288.197, 'text': "So I'm just going to write down what the discrete Fourier transform is, and then I'm going to show you some ways of interpreting this.", 'start': 281.914, 'duration': 6.283}, {'end': 296.921, 'text': "So, for each of these data points, fk, what we're going to be able to do is compute a.", 'start': 289.438, 'duration': 7.483}, {'end': 307.146, 'text': "as you might imagine, what we're going to try to get out of this is some vector of Fourier coefficients f1 hat, f2 hat,", 'start': 296.921, 'duration': 10.225}, {'end': 310.528, 'text': 'f3 hat all the way down to fn hat.', 'start': 307.146, 'duration': 3.382}, {'end': 319.187, 'text': "So just like we took our function f and we turned it into these coefficients that multiplied our cosine and sines, that's what we're doing here.", 'start': 312.884, 'duration': 6.303}, {'end': 326.351, 'text': "We're taking our data f and we're going to obtain this Fourier transform vector f hat of frequency components.", 'start': 319.207, 'duration': 7.144}, {'end': 332.495, 'text': 'So f1 hat will tell me how much of that first low frequency is in the data.', 'start': 326.371, 'duration': 6.124}, {'end': 337.319, 'text': 'f2 hat will tell me how much of that next higher frequency is in the data, and so on and so forth,', 'start': 332.495, 'duration': 4.824}, {'end': 346.247, 'text': 'where fn hat is the highest frequency possible with n data points if it was going as fast as possible oscillating over n data points.', 'start': 337.319, 'duration': 8.928}], 'summary': 'Discrete fourier transform computes fourier coefficients for interpreting data frequency components.', 'duration': 50.581, 'max_score': 281.914, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nl9TZanwbBk/pics/nl9TZanwbBk281914.jpg'}, {'end': 412.189, 'src': 'heatmap', 'start': 379.877, 'weight': 0.738, 'content': [{'end': 381.898, 'text': "I'll walk you through all of these terms here.", 'start': 379.877, 'duration': 2.021}, {'end': 394.922, 'text': 'So the k-th Fourier coefficient is obtained by taking the sum over all j data points at the j-th frequency times the k-th frequency divided by n.', 'start': 382.318, 'duration': 12.604}, {'end': 399.184, 'text': "And I'll tell you what this kind of e to the i 2 pi j k over n means in a minute.", 'start': 394.922, 'duration': 4.262}, {'end': 404.886, 'text': 'But this is how you compute all of those k-th Fourier coefficients.', 'start': 400.204, 'duration': 4.682}, {'end': 412.189, 'text': 'And similarly, just like in a Fourier transform or a Fourier series, if I have my data, I can get my Fourier transform.', 'start': 405.706, 'duration': 6.483}], 'summary': 'Explanation of computing fourier coefficients and transform.', 'duration': 32.312, 'max_score': 379.877, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nl9TZanwbBk/pics/nl9TZanwbBk379877.jpg'}], 'start': 126.381, 'title': 'Discrete fourier transform applications', 'summary': 'Explores the practical applications of discrete fourier transform (dft) in analyzing periodic functions, audio signal analysis for an iphone app, diagnosing car issues, and computing derivatives of data, encompassing the process of obtaining fourier coefficients and reconstructing data.', 'chapters': [{'end': 231.962, 'start': 126.381, 'title': 'Discrete fourier transform in data analysis', 'summary': 'Discusses the use of discrete fourier transform to analyze and approximate periodic functions from discrete data points, and its practical applications in audio signal analysis, with the aim to build an iphone app for identifying audio tones.', 'duration': 105.581, 'highlights': ['The discrete Fourier transform is used to compute the discrete Fourier series of a vector of data, allowing the approximation of underlying continuous functions from discrete measurements.', 'The practical application of Fourier transform in audio data analysis involves identifying tones that contribute to the overall audio signal, illustrating its relevance in building an iPhone app for audio tone detection.', 'The process involves breaking the data vector into a sum of sines and cosines, enabling the extraction of frequency components and patterns from the data, achieving a comprehensive analysis of the audio signal.']}, {'end': 545.741, 'start': 232.482, 'title': 'Discrete fourier transform for data analysis', 'summary': 'Explains the application of discrete fourier transform (dft) in diagnosing car issues and computing derivatives of data, along with the process of obtaining fourier coefficients and reconstructing data through dft.', 'duration': 313.259, 'highlights': ['DFT can diagnose car issues and compute derivatives of data The DFT can diagnose car issues such as belt slipping or abnormal vibrations, and it can be used to approximate derivatives of data.', 'Process of obtaining Fourier coefficients from data The process involves computing a vector of Fourier coefficients f1 hat, f2 hat, f3 hat, etc., which represent the frequency components present in the data.', 'Reconstructing data through DFT The DFT allows for the reconstruction of data from its Fourier transform, enabling the retrieval of original data from its frequency components.']}], 'duration': 419.36, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nl9TZanwbBk/pics/nl9TZanwbBk126381.jpg', 'highlights': ['The practical application of Fourier transform in audio data analysis involves identifying tones that contribute to the overall audio signal, illustrating its relevance in building an iPhone app for audio tone detection.', 'The process involves breaking the data vector into a sum of sines and cosines, enabling the extraction of frequency components and patterns from the data, achieving a comprehensive analysis of the audio signal.', 'The discrete Fourier transform is used to compute the discrete Fourier series of a vector of data, allowing the approximation of underlying continuous functions from discrete measurements.', 'DFT can diagnose car issues such as belt slipping or abnormal vibrations, and it can be used to approximate derivatives of data.', 'The process involves computing a vector of Fourier coefficients f1 hat, f2 hat, f3 hat, etc., which represent the frequency components present in the data.', 'The DFT allows for the reconstruction of data from its Fourier transform, enabling the retrieval of original data from its frequency components.']}, {'end': 1054.338, 'segs': [{'end': 592.429, 'src': 'heatmap', 'start': 545.741, 'weight': 0.92, 'content': [{'end': 551.662, 'text': 'okay, this is, And this defines a fundamental frequency.', 'start': 545.741, 'duration': 5.921}, {'end': 555.266, 'text': 'This defines some omega n,', 'start': 551.702, 'duration': 3.564}, {'end': 566.979, 'text': 'which is some fundamental frequency that is related to what kinds of sines and cosines I can approximate with n discrete values in a domain x.', 'start': 555.266, 'duration': 11.713}, {'end': 569.862, 'text': 'So this is kind of the fundamental frequency we get to work with.', 'start': 566.979, 'duration': 2.883}, {'end': 573.184, 'text': 'if I have an interval with n data points.', 'start': 570.623, 'duration': 2.561}, {'end': 580.425, 'text': 'And all of these Fourier transforms are adding up integer multiples of that fundamental frequency times my data.', 'start': 574.164, 'duration': 6.261}, {'end': 582.966, 'text': 'And the same thing with my inverse Fourier transform.', 'start': 580.886, 'duration': 2.08}, {'end': 592.429, 'text': "So we're going to be able to use this fundamental frequency omega n to compute a matrix that would multiply my data and give me my Fourier transform.", 'start': 583.966, 'duration': 8.463}], 'summary': 'Fundamental frequency omega n is used to compute a matrix for fourier transform.', 'duration': 46.688, 'max_score': 545.741, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nl9TZanwbBk/pics/nl9TZanwbBk545741.jpg'}, {'end': 829.63, 'src': 'heatmap', 'start': 800.996, 'weight': 0.862, 'content': [{'end': 806.04, 'text': 'for j equals zero, I get e to the zero is one okay?', 'start': 800.996, 'duration': 5.044}, {'end': 812.198, 'text': 'For j equals 1, I get e to the minus 2.', 'start': 808.015, 'duration': 4.183}, {'end': 814.139, 'text': 'pi i divided by n.', 'start': 812.198, 'duration': 1.941}, {'end': 814.76, 'text': 'Remember, k is 1.', 'start': 814.139, 'duration': 0.621}, {'end': 816.1, 'text': "So that's just omega.", 'start': 814.76, 'duration': 1.34}, {'end': 825.066, 'text': 'When j equals 2, I get basically omega squared.', 'start': 819.163, 'duration': 5.903}, {'end': 829.63, 'text': 'I get e to the minus 2 pi i times 2 divided by n.', 'start': 825.086, 'duration': 4.544}], 'summary': 'Transcript covers calculations for j=0, 1, 2 with e and pi, and omega.', 'duration': 28.634, 'max_score': 800.996, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nl9TZanwbBk/pics/nl9TZanwbBk800996.jpg'}, {'end': 1002.45, 'src': 'heatmap', 'start': 935.414, 'weight': 1, 'content': [{'end': 938.077, 'text': 'But because this is defined on discrete data.', 'start': 935.414, 'duration': 2.663}, {'end': 945.461, 'text': 'I can write it as a big matrix operation okay, so this here is a The DFT matrix.', 'start': 938.198, 'duration': 7.263}, {'end': 949.083, 'text': 'This is the DFT, the discrete Fourier transform matrix.', 'start': 945.681, 'duration': 3.402}, {'end': 954.427, 'text': 'And if you had your vector of data, you multiply it by this matrix, you get your Fourier transform out.', 'start': 949.624, 'duration': 4.803}, {'end': 955.988, 'text': 'Very, very useful.', 'start': 955.107, 'duration': 0.881}, {'end': 962.212, 'text': "And these Fourier coefficients, you'll notice that this is a complex number.", 'start': 957.249, 'duration': 4.963}, {'end': 965.794, 'text': 'This has a cosine plus an i sine part.', 'start': 962.232, 'duration': 3.562}, {'end': 966.915, 'text': 'This is a complex number.', 'start': 965.814, 'duration': 1.101}, {'end': 969.277, 'text': 'So this is a complex matrix.', 'start': 967.716, 'duration': 1.561}, {'end': 973.72, 'text': 'And these Fourier coefficients, these blue Fourier coefficients are complex valued.', 'start': 969.817, 'duration': 3.903}, {'end': 983.803, 'text': 'And so these somehow tell you how much of that zeroth mode, cosine and sine mode, there are, but it also tells you the phase.', 'start': 974.6, 'duration': 9.203}, {'end': 991.046, 'text': 'So the magnitude of this complex number tells you how much magnitude of that first mode you have.', 'start': 984.303, 'duration': 6.743}, {'end': 1002.45, 'text': 'And then the phase angle of that complex number tells you how much cosine or how much sine or what phase in between your sine and cosine is.', 'start': 991.766, 'duration': 10.684}], 'summary': 'Discrete fourier transform matrix used to obtain fourier transform of data, yielding complex-valued coefficients.', 'duration': 48.389, 'max_score': 935.414, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nl9TZanwbBk/pics/nl9TZanwbBk935414.jpg'}, {'end': 1054.338, 'src': 'embed', 'start': 1033.654, 'weight': 0, 'content': [{'end': 1041.56, 'text': "And so what I'm going to show you in the next few lectures is how you compute this efficiently using the fast Fourier transform.", 'start': 1033.654, 'duration': 7.906}, {'end': 1044.321, 'text': 'So you never actually have to build this matrix and do this multiplication.', 'start': 1041.579, 'duration': 2.742}, {'end': 1046.483, 'text': "This is how it's mathematically defined.", 'start': 1044.762, 'duration': 1.721}, {'end': 1051.989, 'text': "But computationally, we're always going to compute the DFT using the fast Fourier transform algorithm.", 'start': 1046.824, 'duration': 5.165}, {'end': 1053.715, 'text': "Okay, that's all coming up soon.", 'start': 1052.549, 'duration': 1.166}, {'end': 1054.338, 'text': 'Thank you.', 'start': 1054.056, 'duration': 0.282}], 'summary': 'Efficient computation of dft using fft algorithm.', 'duration': 20.684, 'max_score': 1033.654, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nl9TZanwbBk/pics/nl9TZanwbBk1033654.jpg'}], 'start': 545.741, 'title': 'Fourier transforms', 'summary': 'Covers fundamental frequency, fourier transform using matrix operations, discrete fourier transform, complex-valued fourier coefficients, and computational efficiency of the fast fourier transform algorithm.', 'chapters': [{'end': 659.735, 'start': 545.741, 'title': 'Fundamental frequency and fourier transforms', 'summary': 'Discusses the fundamental frequency omega n, which is used to compute a matrix for the fourier transform, allowing for approximation of sines and cosines with n discrete values. it explains the process of computing the fourier transform and inverse fourier transform using matrix operations instead of tedious for loops.', 'duration': 113.994, 'highlights': ['The fundamental frequency omega n is used to compute a matrix for the Fourier transform, allowing for approximation of sines and cosines with n discrete values.', 'The process of computing the Fourier transform and inverse Fourier transform is explained in terms of matrix operations using the fundamental frequencies omega n, avoiding the need for tedious for loops.', 'The chapter emphasizes the importance of the fundamental frequency omega n in working with Fourier transforms and efficiently computing them using matrix operations.']}, {'end': 1054.338, 'start': 659.795, 'title': 'Discrete fourier transform', 'summary': 'Explains the concept of discrete fourier transform, the matrix operation involved, and the significance of complex-valued fourier coefficients. it also mentions the computational efficiency provided by the fast fourier transform algorithm.', 'duration': 394.543, 'highlights': ['The discrete Fourier transform (DFT) matrix can be used to compute the Fourier transform of a vector of data, providing a useful tool for analyzing discrete data. The DFT matrix allows for the computation of the Fourier transform of data, making it a valuable tool for analyzing discrete datasets.', 'The complex-valued Fourier coefficients derived from the DFT matrix provide information about the magnitude and phase of the cosine and sine modes, enabling the approximation of the original data. The complex-valued Fourier coefficients obtained from the DFT matrix reveal information about the magnitude and phase of the cosine and sine modes, aiding in the accurate approximation of the original data.', 'The computational efficiency of the discrete Fourier transform is enhanced by the fast Fourier transform algorithm, which eliminates the need for explicitly building and multiplying the DFT matrix. The computational efficiency of the discrete Fourier transform is improved by the fast Fourier transform algorithm, eliminating the necessity to explicitly construct and multiply the DFT matrix.']}], 'duration': 508.597, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/nl9TZanwbBk/pics/nl9TZanwbBk545741.jpg', 'highlights': ['The computational efficiency of the discrete Fourier transform is improved by the fast Fourier transform algorithm, eliminating the necessity to explicitly construct and multiply the DFT matrix.', 'The complex-valued Fourier coefficients obtained from the DFT matrix reveal information about the magnitude and phase of the cosine and sine modes, aiding in the accurate approximation of the original data.', 'The discrete Fourier transform (DFT) matrix can be used to compute the Fourier transform of a vector of data, providing a useful tool for analyzing discrete data.']}], 'highlights': ['The fast Fourier transform (FFT) is one of the most important algorithms today, used for image compression, audio compression, signal processing, and high performance scientific computing.', 'The DFT is an extremely important concept and is eventually used to compute the FFT, which scales to very large data sets and is a computationally efficient way of computing the DFT.', 'The discrete Fourier transform (DFT) is a mathematical transformation that can be written in terms of a big matrix multiplication.', 'The practical application of Fourier transform in audio data analysis involves identifying tones that contribute to the overall audio signal, illustrating its relevance in building an iPhone app for audio tone detection.', 'The process involves breaking the data vector into a sum of sines and cosines, enabling the extraction of frequency components and patterns from the data, achieving a comprehensive analysis of the audio signal.', 'The discrete Fourier transform is used to compute the discrete Fourier series of a vector of data, allowing the approximation of underlying continuous functions from discrete measurements.', 'The computational efficiency of the discrete Fourier transform is improved by the fast Fourier transform algorithm, eliminating the necessity to explicitly construct and multiply the DFT matrix.', 'The complex-valued Fourier coefficients obtained from the DFT matrix reveal information about the magnitude and phase of the cosine and sine modes, aiding in the accurate approximation of the original data.']}