Discrete Fourier Transform by hand ✍️ ~ 12 steps walkthrough below
Tom Yeh
Visit on X@ProfTomYeh65K followers
25,684 views
Discrete Fourier Transform by hand ✍️ ~ 12 steps walkthrough below
Here is a little-known secret about the DFT and the inverse DFT: it is just matrix multiplication in both directions, one the transpose of the other, exactly like the forward pass and backpropagation I drew in other examples.
Goal: recover which cosine waves a signal is made of, using nothing but multiplication and addition.
= 1. Given =
Three signals written as sums of cosines, and a fourth, X, that we do not know yet.
= 2. Frequency matrix F =
Let us write the coefficients as a matrix. Each signal is a row, each frequency a column, so A = cos(w) + 2cos(2w) becomes [1, 2, 0, 0].
= 3. Sample the waves =
We read the four cosine waves at ten discrete time points. That word "discrete" is the whole difference between this and the continuous transform.
= 4. Cosine matrix W =
Let us write those samples as a matrix: each frequency a row, each time point a column.
= 5. Frequency to time =
We multiply F by W. That combines the four cosine waves in the proportions F specifies, and the result T is the three signals as they would look in time.
= 6. Transpose =
Let us stand each signal up as a column.
= 7. Time to frequency =
We multiply W by that transpose. Every cell is the dot product of one signal with one cosine wave, which measures how much of that wave the signal contains. Zero means none of it.
= 8. Scale =
Let us multiply by 2/n, with n = 10. The projections come out five times too large, and this is the correction.
= 9. Transpose back =
We turn it back around, and it is F again, exactly. That is the check: the transform recovered the coefficients we started from.
= 10. Now solve for X =
Let us run the same multiplication on the one signal whose recipe we never knew.
= 11. Scale =
We divide by 5 again.
= 12. Transpose back =
And X reads [0, 0, 3, 2], which says X = 3cos(3w) + 2cos(4w).
Note: I originally drew this to show that the DFT is a special case of a convolution layer, its filters fixed to sine and cosine waves rather than learned. No wonder, then, that a convolution layer free to learn its own filters can be trained to process signals.
💾 Save this post!
Comments
Comments from the original post on X (Twitter)
No comments yet
