Discrete Fourier Transform by Hand

Discrete Fourier Transform by Hand ✍️ Calculating AI by Hand: 19 of 28 Library › Calculating AI by Hand ✍️ Matrix Multiplication by Hand ✍️ Matrix Multiplication by Hand ✍️ Multi Layer Perceptron (MLP) by Hand ✍️ Multi Layer Perceptron (MLP) by Hand ✍️ Backpropagation by Hand ✍️ Backpropagation by Hand ✍️ SVM by Hand ✍️ SVM by Hand ✍️ Batch Normalization by Hand ✍️ Batch Normalization by Hand ✍️ Dropout by Hand ✍️ Dropout by Hand ✍️ Recurrent Neural Network (RNN) by Hand ✍️ Recurrent Neural Network (RNN) by Hand ✍️ LSTM by Hand ✍️ LSTM by Hand ✍️ Deep RNN by Hand ✍️ Deep RNN by Hand ✍️ Self Attention by Hand ✍️ Self Attention by Hand ✍️ Transformer by Hand ✍️ Transformer by Hand ✍️ Autoencoder by Hand ✍️ Autoencoder by Hand ✍️ Variational Auto Encoder (VAE) by Hand ✍️ Variational Auto Encoder (VAE) by Hand ✍️ Sparse Auto Encoder (SAE) by Hand ✍️ Sparse Auto Encoder (SAE) by Hand ✍️ Generative Adversarial Network (GAN) by Hand ✍️ Generative Adversarial Network (GAN) by Hand ✍️ Sampling a Sentence by Hand ✍️ Sampling a Sentence by Hand ✍️ Residual Network by Hand ✍️ Residual Network by Hand ✍️ U-Net by Hand ✍️ U-Net by Hand ✍️ Discrete Fourier Transform by Hand ✍️ Discrete Fourier Transform by Hand ✍️ Graph Convolutional Network (GCN) by Hand ✍️ Graph Convolutional Network (GCN) by Hand ✍️ CLIP by Hand ✍️ CLIP by Hand ✍️ Vector Database by Hand ✍️ Vector Database by Hand ✍️ Mixture of Experts (MoE) by Hand ✍️ Mixture of Experts (MoE) by Hand ✍️ Switch Transformer by Hand ✍️ Switch Transformer by Hand ✍️ Mamba's S6 by Hand ✍️ Mamba's S6 by Hand ✍️ Sora's Diffusion Transformer (DiT) by Hand ✍️ Sora's Diffusion Transformer (DiT) by Hand ✍️ BitNet by Hand ✍️ BitNet by Hand ✍️ Reinforcement Learning with Human Feedback (RLHF) by Hand ✍️ Reinforcement Learning with Human Feedback (RLHF) by Hand ✍️ In signal processing, the Discrete Fourier Transform (DFT) is no doubt the most important method. But the math involved is extremely complex, literally, involving a summation over a complex number term e^(-iwt), where e is the Euler number, i is the imaginary unit, w is the angular frequency, and t is time. I developed this exercise to demonstrate that underneath such complexity, DFT is just a series of matrix multiplications you can calculate by hand. ✍️ Once you see that, it should not surprise you that a deep neural network, which is also a series of matrix multiplications, with activation functions in-between, can learn to perform DFT to process and analyze signals so effectively. 💡 Learned vs. Fixed: U-Net learns its filters from data to process a signal in the spatial domain. The DFT is the classical opposite, a fixed transform, designed by hand rather than learned, that views the same signal in the frequency domain as a combination of cosine waves. How does DFT work? Setup Step 1 of 12: Given Signals A, B, and C in the 🟧 frequency domain: Signals A, B, and C in the 🟧 frequency domain: A = cos(w) + 2cos(2w) A = cos(w) + 2cos(2w) B = cos(w) + cos(3w) + cos(4w) B = cos(w) + cos(3w) + cos(4w) C = -cos(2w) + cos(3w) C = -cos(2w) + cos(3w) Each signal is a weighed sum of four cosine waves at frequencies 1w, 2w, 3w, and 4w. Each signal is a weighed sum of four cosine waves at frequencies 1w, 2w, 3w, and 4w. We will apply Inverse DFT to convert the signals to time domain representations, and then demonstrate DFT can convert back to their original frequency domain representations. We will apply Inverse DFT to convert the signals to time domain representations, and then demonstrate DFT can convert back to their original frequency domain representations. Signal X in the 🟩 time domain. X is sampled at 10 time points 1t, 2t, …, 10t: Signal X in the 🟩 time domain. X is sampled at 10 time points 1t, 2t, …, 10t: X = [-2.5, -1.8, 3, -0.7, -1.0, -0.7, 3, -1.8, -2.5, 5] X = [-2.5, -1.8, 3, -0.7, -1.0, -0.7, 3, -1.8, -2.5, 5] Suppose X is also a weighted sum of the same four cosine waves, but we don’t already know their weights. We will apply DFT to discover them. Suppose X is also a weighted sum of the same four cosine waves, but we don’t already know their weights. We will apply DFT to discover them. Step 2 of 12: Frequency Matrix (F) Write the coefficients of A, B, C as a matrix F. Each signal is a row. Each frequency is a column. Write the coefficients of A, B, C as a matrix F. Each signal is a row. Each frequency is a column. A → [1, 2, 0, 0] A → [1, 2, 0, 0] B → [1, 0, 1, 1] B → [1, 0, 1, 1] C → [0, -1, 1, 0] C → [0, -1, 1, 0] Step 3 of 12: Cosine → Discrete Sample from the continuous cosine waves at discrete time points 1t, 2t, 3t, to 10t. Sample from the continuous cosine waves at discrete time points 1t, 2t, 3t, to 10t. This post is for paid subscribers