Lesson overview | Previous part | Next part

Fourier Transform: Appendix B: Worked Examples and Techniques to Appendix F: The Fourier Transform in Practice - Case Studies

Appendix B: Worked Examples and Techniques

B.1 The Fourier Transform Table - Complete Reference

The following table lists the most important Fourier Transform pairs, using the $\xi$-convention $\hat{f}(\xi) = \int f(t)e^{-2\pi i\xi t}\,dt$. All functions are assumed in $L^1 \cap L^2$ unless otherwise noted.

B.2 Four Full Worked Examples

Worked Example 1: Triangular Pulse

The triangular function $\Lambda(t) = \max(1 - |t|, 0)$ is zero outside $[-1, 1]$. We compute $\hat{\Lambda}$ directly.

$$\hat{\Lambda}(\xi) = \int_{-1}^{0}(1+t)e^{-2\pi i\xi t}\,dt + \int_0^1(1-t)e^{-2\pi i\xi t}\,dt$$

For the first integral, let $u = -t$:

$$\int_{-1}^{0}(1+t)e^{-2\pi i\xi t}\,dt = \int_0^1(1-u)e^{2\pi i\xi u}\,du$$

Adding both integrals: $\hat{\Lambda}(\xi) = \int_0^1(1-t)(e^{2\pi i\xi t}+e^{-2\pi i\xi t})\,dt = 2\int_0^1(1-t)\cos(2\pi\xi t)\,dt$.

Integrating by parts:

$$= 2\left[\frac{(1-t)\sin(2\pi\xi t)}{2\pi\xi}\right]_0^1 + 2\int_0^1\frac{\sin(2\pi\xi t)}{2\pi\xi}\,dt = 0 + \frac{1}{\pi\xi}\left[-\frac{\cos(2\pi\xi t)}{2\pi\xi}\right]_0^1 = \frac{1-\cos(2\pi\xi)}{2\pi^2\xi^2}$$

Using $1 - \cos\theta = 2\sin^2(\theta/2)$:

$$\hat{\Lambda}(\xi) = \frac{2\sin^2(\pi\xi)}{2\pi^2\xi^2} = \left(\frac{\sin(\pi\xi)}{\pi\xi}\right)^2 = \operatorname{sinc}^2(\xi)$$

The triangular pulse is the FT of $\operatorname{sinc}^2$. Alternatively: $\Lambda = \operatorname{rect} * \operatorname{rect}$ (convolution of two rect functions), so $\hat{\Lambda} = \hat{\operatorname{rect}}\cdot\hat{\operatorname{rect}} = \operatorname{sinc}^2$ by the convolution theorem. The $\operatorname{sinc}^2$ spectrum decays faster than $\operatorname{sinc}$ (as $1/\xi^2$ vs $1/\xi$) because $\Lambda$ is continuous (no jumps), while $\operatorname{rect}$ has jump discontinuities.

Worked Example 2: Gaussian via Differential Equation

An elegant alternative proof that $\mathcal{F}[e^{-\pi t^2}] = e^{-\pi\xi^2}$ uses the fact that $f(t) = e^{-\pi t^2}$ satisfies $f'(t) = -2\pi t\,f(t)$.

Taking the FT of both sides and using the differentiation rules:

• LHS: $\mathcal{F}[f'](\xi) = 2\pi i\xi\,\hat{f}(\xi)$
• RHS: $\mathcal{F}[-2\pi t\,f(t)](\xi) = -2\pi\cdot\frac{1}{-2\pi i}\frac{d}{d\xi}\hat{f}(\xi) = -i\hat{f}'(\xi)$

Wait - use: $\mathcal{F}[tf(t)](\xi) = \frac{1}{-2\pi i}\frac{d}{d\xi}\hat{f}(\xi) = \frac{i}{2\pi}\hat{f}'(\xi)$

So $2\pi i\xi\,\hat{f}(\xi) = -2\pi\cdot\frac{i}{2\pi}\hat{f}'(\xi) = -i\hat{f}'(\xi)$.

This gives the ODE: $\hat{f}'(\xi) = -2\pi\xi\,\hat{f}(\xi)$, with solution $\hat{f}(\xi) = C\,e^{-\pi\xi^2}$.

To find $C$: $\hat{f}(0) = \int e^{-\pi t^2}\,dt = 1$ (Gaussian integral). So $C = 1$ and $\hat{f}(\xi) = e^{-\pi\xi^2}$. $\square$

This proof is superior for teaching: it shows that the Gaussian's self-duality follows from the fact that $e^{-\pi t^2}$ satisfies the simplest possible first-order ODE, and the FT converts this ODE into the same ODE in frequency space.

Worked Example 3: FT of $e^{-a|t|}$ and a Contour Argument

$$\hat{f}(\xi) = \int_{-\infty}^\infty e^{-a|t|}e^{-2\pi i\xi t}\,dt = \int_0^\infty e^{-at}e^{-2\pi i\xi t}\,dt + \int_{-\infty}^0 e^{at}e^{-2\pi i\xi t}\,dt$$

For the first integral ($t > 0$):

$$\int_0^\infty e^{-(a+2\pi i\xi)t}\,dt = \frac{1}{a+2\pi i\xi} \quad \text{(valid for } \operatorname{Re}(a+2\pi i\xi) = a > 0\text{)}$$

For the second integral, let $u = -t$ ($u > 0$, $t < 0$):

$$\int_0^\infty e^{-au}e^{2\pi i\xi u}\,du = \frac{1}{a-2\pi i\xi}$$

Therefore:

$$\hat{f}(\xi) = \frac{1}{a+2\pi i\xi} + \frac{1}{a-2\pi i\xi} = \frac{(a-2\pi i\xi)+(a+2\pi i\xi)}{a^2+(2\pi\xi)^2} = \frac{2a}{a^2+4\pi^2\xi^2}$$

This is a Lorentzian (Cauchy distribution) centered at $\xi = 0$ with half-width $a/(2\pi)$. As $a \to 0^+$, the time-domain signal $e^{-a|t|}$ approaches the constant $1$, and its Fourier Transform approaches $2/(4\pi^2\xi^2)\cdot2a \to 2\pi\delta(\xi)/\pi = 2\delta(\xi)$... Actually: $\frac{2a}{a^2+4\pi^2\xi^2} \to \frac{1}{2\pi}\cdot\frac{2\pi a}{\pi[a^2+4\pi^2\xi^2]/(2\pi)} \to$ ... more carefully, $\frac{a}{\pi(a^2+4\pi^2\xi^2)}\cdot 2\pi$ and $\frac{a}{\pi(a^2+\xi^2)} \to \delta(\xi)$ is the standard Poisson kernel. The limit confirms $\mathcal{F}[1] = \delta$.

Worked Example 4: The FT and Convolution for the Heat Equation Kernel

The heat kernel at time $t > 0$ is $G_t(x) = \frac{1}{\sqrt{4\pi\kappa t}}e^{-x^2/(4\kappa t)}$. We verify $\mathcal{F}[G_t](\xi) = e^{-4\pi^2\kappa t\xi^2}$ using the scaling theorem.

We know $\mathcal{F}[e^{-\pi x^2}](\xi) = e^{-\pi\xi^2}$. The heat kernel is:

$$G_t(x) = \frac{1}{\sqrt{4\pi\kappa t}}e^{-x^2/(4\kappa t)} = \frac{1}{\sqrt{4\pi\kappa t}}\cdot e^{-\pi(x/\sigma)^2/\pi}\cdot\frac{1}{\sigma}...$$

More directly: write $G_t(x) = \frac{1}{\sqrt{4\pi\kappa t}}e^{-x^2/(4\kappa t)}$. Setting $\sigma = \sqrt{2\kappa t}$:

$$G_t(x) = \frac{1}{\sqrt{2\pi}\sigma}e^{-x^2/(2\sigma^2)}$$

The FT of a Gaussian $\frac{1}{\sqrt{2\pi}\sigma}e^{-x^2/(2\sigma^2)}$ is $e^{-2\pi^2\sigma^2\xi^2}$... Using our convention:

$\mathcal{F}[e^{-\pi x^2/\sigma^2}](\xi) = \sigma e^{-\pi\sigma^2\xi^2}$, so $\mathcal{F}\!\left[\frac{1}{\sigma}e^{-\pi x^2/\sigma^2}\right](\xi) = e^{-\pi\sigma^2\xi^2}$.

For $G_t$: $G_t(x) = \frac{1}{\sigma_t}e^{-\pi x^2/\sigma_t^2}$ where $\sigma_t = 2\sqrt{\pi\kappa t}$... Let me just directly compute:

Write $G_t(x) = ce^{-\alpha x^2}$ with $c = (4\pi\kappa t)^{-1/2}$, $\alpha = 1/(4\kappa t)$. Using $\mathcal{F}[e^{-\alpha x^2}](\xi) = \sqrt{\pi/\alpha}\,e^{-\pi^2\xi^2/\alpha}$:

$$\mathcal{F}[G_t](\xi) = c\sqrt{\frac{\pi}{\alpha}}e^{-\pi^2\xi^2/\alpha} = \frac{1}{\sqrt{4\pi\kappa t}}\cdot\sqrt{4\pi\kappa t}\cdot e^{-\pi^2\xi^2\cdot 4\kappa t} = e^{-4\pi^2\kappa t\xi^2}$$

This confirms that in the $\xi$-convention, the heat kernel's FT is $e^{-4\pi^2\kappa t\xi^2}$ - exactly the solution we derived from the heat equation in Section A.4.

B.3 Decay Rates and Smoothness: The Complete Picture

The relationship between smoothness of $f$ and decay of $\hat{f}$ is one of the deepest qualitative results in Fourier analysis. The complete picture:

Theorem B.1 (Smoothness Spectral Decay). Let $f \in L^1(\mathbb{R})$.

| Condition on $f$ | Decay of $|\hat{f}(\xi)|$ as $|\xi| \to \infty$ | |-----------------|----------------------------------------------| | $f$ has a jump discontinuity | $O(1/|\xi|)$ | | $f \in C^1$ (continuous, one derivative) | $o(1/|\xi|)$ | | $f \in C^k$, $f^{(k)} \in L^1$ | $O(1/|\xi|^k)$ | | $f \in C^\infty$ | Faster than any polynomial: $O(1/|\xi|^N)$ for all $N$ | | $f$ analytic (holomorphic in a strip $|\operatorname{Im}(t)| < \delta$) | Exponential decay: $O(e^{-2\pi\delta|\xi|})$ |

Proof sketch: For the $k$-derivative case: $|\hat{f}(\xi)| = |\mathcal{F}[f^{(k)}](\xi)|/|2\pi i\xi|^k \leq \lVert f^{(k)}\rVert_1/(2\pi|\xi|)^k$. For the analytic case, shift the contour of integration to $\operatorname{Im}(t) = \pm\delta$ (for $\xi \gtrless 0$) gaining an exponential factor $e^{\mp 2\pi\xi\delta} = e^{-2\pi|\xi|\delta}$. $\square$

Applications:

• Signal compression: Smooth signals (like audio with no sharp transients) have rapidly decaying spectra -> can be compressed by truncating high frequencies with small error.
• Neural network generalization: Smooth target functions (natural image statistics) have rapidly decaying spectra -> a network with limited bandwidth can approximate them well. This connects to the spectral bias of neural networks (Rahaman et al., 2019): networks preferentially learn low-frequency components first.
• Discretization error: The aliasing error when sampling a signal at rate $T$ is bounded by $\sum_{n \neq 0} |\hat{f}(\xi + n/T)| \leq C/T^k$ if $f \in C^k$ - smoother signals alias less.

B.4 The Fourier Transform in Different Function Spaces

A complete picture of where the FT lives:

DOMAIN OF DEFINITION - FOURIER TRANSFORM
========================================================================

  L1(R)    ->  C0(R)        (bounded, continuous, vanishes at infty)
               f_infty <= f_1

  L2(R)    ->  L2(R)        (Plancherel: FT is unitary)
               f_2 = f_2

  L1  L2  ->  L2           (both apply; easiest to work with)

  S(R)     ->  S(R)         (Schwartz space: FT preserves rapidly
              (bijection)    decreasing smooth functions)

  S'(R)    ->  S'(R)        (tempered distributions: largest domain)
              (bijection)    includes , constants, periodic signals

  Key inclusions:  S  L1  L2  L1  S'
                   S  L1  L2  L2  S'

  For practical computation: work in S' (distributions),
  which unifies all cases under one theory.

========================================================================

B.5 Numerical Computation of the Fourier Transform

In practice, the Fourier Transform is computed numerically via the DFT/FFT (Section 20-03). Here we note the key relationships.

Approximation scheme. To numerically approximate $\hat{f}(\xi)$ for $f \in L^1(\mathbb{R})$:

1. Truncate the signal to $[-L, L]$ for large enough $L$ (error: $\int_{|t|>L}|f(t)|\,dt$)
2. Sample at rate $N/(2L)$ to get $N$ equally-spaced samples $f_n = f(nT)$ where $T = 2L/N$
3. Apply DFT: $\hat{f}_k = T\sum_{n=0}^{N-1}f_n e^{-2\pi ink/N}$
4. The result approximates $\hat{f}(k/(2L))$ for $k = 0, 1, \ldots, N/2$.

Sources of error:

• Aliasing: Undersampling causes high-frequency components to fold back - reduced by sampling faster (higher $N$)
• Leakage: Truncation at $\pm L$ multiplies by a rect function -> convolves spectrum with sinc -> spectral leakage. Reduced by windowing (multiplying by a smooth window before DFT)
• Resolution: The frequency resolution is $1/(2L)$ - the smallest frequency distinguishable in the DFT is $1/(2L)$. For finer resolution, use longer time windows.

All three error types are direct consequences of the Fourier Transform properties developed in this section. Full treatment in Section 20-03.

---

Appendix C: Connections, Extensions, and Deep Dives

C.1 The Fourier Transform on Locally Compact Abelian Groups

The Fourier Transform generalizes far beyond $\mathbb{R}$. For any locally compact abelian (LCA) group $G$ with Haar measure $\mu$, there is a Fourier Transform $\mathcal{F}: L^1(G) \to C_0(\hat{G})$ where $\hat{G}$ is the Pontryagin dual group (the group of continuous homomorphisms $G \to S^1$).

Plancherel's theorem, the convolution theorem, and the inversion theorem all hold in this general setting. The unification of Fourier series and Fourier Transform as special cases of the same construction on different groups is one of the most elegant results in abstract harmonic analysis.

For AI: The group structure is what makes RoPE work. The circle group $S^1$ (the group of complex numbers of modulus 1 under multiplication) is a compact abelian group. Multiplying by $e^{im\theta}$ is the group action of rotation by $m\theta$. The relative-position property of RoPE $\langle e^{im\theta}q, e^{in\theta}k\rangle = e^{i(m-n)\theta}\langle q,k\rangle$ is the statement that the group action is transitive: the inner product only sees the group element $e^{i(m-n)\theta}$ corresponding to relative position.

C.2 Non-Commutative Fourier Analysis

For non-abelian groups (e.g., $SO(3)$, permutation groups $S_N$), the Pontryagin duality breaks down but a Fourier Transform still exists, with irreducible unitary representations playing the role of frequencies.

Graph Fourier Transform: For a graph $G = (V, E)$ with Laplacian $L = D - A$ (where $D$ is the degree matrix), the eigenvectors $L\mathbf{u}_k = \lambda_k\mathbf{u}_k$ play the role of complex exponentials. The graph Fourier Transform is $\hat{\mathbf{f}} = U^\top\mathbf{f}$ where $U = [\mathbf{u}_1,\ldots,\mathbf{u}_N]$ is the matrix of eigenvectors. The eigenvalues $\lambda_k$ represent "graph frequencies" - how rapidly the eigenvector oscillates across the graph.

This is the foundation of spectral graph neural networks (Bruna et al., 2014; Defferrard et al., 2016 ChebNet; Kipf & Welling, 2017 GCN). The spectral GNN applies a learned filter $h_\theta(\Lambda)$ in graph Fourier space: $\hat{h}_\theta * \mathbf{f} = U\,h_\theta(\Lambda)\,U^\top\mathbf{f}$.

Full treatment in Section 11-04 Spectral Graph Theory.

C.3 The Fourier Transform and Learning Theory

The Fourier Transform connects deeply to several foundational results in learning theory:

Spectral Bias (Rahaman et al., 2019): Neural networks trained by gradient descent learn the Fourier components of the target function in order of increasing frequency. This is because the NTK (Neural Tangent Kernel) has eigenvalues that decay rapidly with frequency - the network converges faster on low-frequency components. Consequence: networks generalize well on smooth targets and may overfit on high-frequency features.

Frequency Principle: Let $f^*$ be the target function and $f_t$ the network at training step $t$. Then $|\hat{f}_t(\xi) - \hat{f}^*(\xi)|$ decreases at rate $\propto \lambda_\xi$ (the NTK eigenvalue at frequency $\xi$), and $\lambda_\xi$ decreases with $|\xi|$. High-frequency components therefore converge last.

Implications:

• Data augmentation that adds high-frequency perturbations (e.g., random cropping, noise injection) improves generalization precisely because it forces the network to represent these frequencies.
• Adversarial examples often correspond to high-frequency perturbations of inputs that fool the network but are invisible to humans - the network hasn't fully learned the high-frequency structure.
• Neural networks with spectral inductive bias (e.g., SIREN - sinusoidal activation functions) can represent high-frequency targets more efficiently.

Rademacher Complexity and Fourier Norms: The generalization error of a hypothesis class can be bounded by its Fourier $\ell^1$ norm: $\sum_\xi |\hat{f}(\xi)|$. Functions with small Fourier $\ell^1$ norm have low complexity and generalize well. This connects to the theory of Barron functions (Barron, 1993): functions $f$ with $\int|\hat{f}(\xi)||\xi|\,d\xi < C$ can be approximated to accuracy $\epsilon$ by a two-layer neural network with $O(C^2/\epsilon^2)$ neurons.

C.4 Phase Retrieval - When Magnitude Alone Is Insufficient

The FT $\hat{f}(\xi) = |\hat{f}(\xi)|e^{i\phi(\xi)}$ consists of a magnitude $|\hat{f}(\xi)|$ and a phase $\phi(\xi)$. Phase retrieval asks: can you recover $f$ from $|\hat{f}|$ alone (without the phase)?

In general, the answer is no - many different signals can have the same magnitude spectrum. For example, $f(t)$ and $f(-t)$ have the same magnitude spectrum $|\hat{f}(\xi)|$ but may be entirely different. More strikingly, phase-randomized images (keeping $|\hat{f}|$ but using random $\phi(\xi)$) look like noise - the phase carries most of the perceptual information.

Phase is more important than magnitude for perception: An experiment: take image $A$ and image $B$, swap their phase spectra (keep $A$'s magnitude, use $B$'s phase), and reconstruct. The result looks like image $B$ - demonstrating that phase dominates perception.

For AI: This has implications for:

• Adversarial robustness: Many adversarial attacks perturb the high-frequency phase of input images - imperceptible to humans but highly disruptive to CNNs.
• Generative models: Diffusion models and GANs must learn both the magnitude and phase of the data distribution's spectrum to generate perceptually realistic images.
• FNet limitation: FNet takes the real part of the FT output, effectively discarding half the phase information. This is one reason FNet performs worse than attention on tasks requiring precise token interactions.

C.5 Fast Algorithms Beyond FFT

The FFT computes the $N$-point DFT in $O(N\log N)$ operations, a vast improvement over the naive $O(N^2)$. Several modern algorithms push further:

Sparse FFT: If the signal has only $k \ll N$ significant frequencies, the sparse FFT (Hassanieh et al., 2012; adopted in MIT SFFT) computes the DFT in $O(k\log N)$ - sublinear in $N$. Applications: energy-efficient spectrum sensing, MRI acceleration.

Non-Uniform FFT (NUFFT): The standard FFT requires uniformly-spaced samples. The NUFFT handles non-uniform grids with $O(N\log N)$ complexity, using oversampling and interpolation. Used in MRI reconstruction (non-Cartesian k-space trajectories) and radio astronomy.

Butterfly factorization (Monarch matrices): The FFT matrix can be written as a product of $O(\log N)$ sparse matrices (butterfly factors), each requiring $O(N)$ operations. Monarch matrices (Dao et al., 2022) generalize this structure for learned efficient linear layers - they can represent any matrix with $O(N\sqrt{N})$ parameters that can be applied in $O(N\sqrt{N})$ time, interpolating between dense matrices ($O(N^2)$) and diagonal ($O(N)$).

The FFT algorithm and its applications - Cooley-Tukey, Bluestein, Rader - are covered in full in Section 20-03 DFT and FFT.

C.6 Summary: The Central Theorems of the Fourier Transform

This section has developed the following central results, in order of importance:

1. Definition and well-posedness (Section 2):

$$\hat{f}(\xi) = \int_{-\infty}^\infty f(t)e^{-2\pi i\xi t}\,dt, \qquad f \in L^1(\mathbb{R})$$

Well-defined, bounded, continuous. Riemann-Lebesgue: $\hat{f}(\xi) \to 0$ as $|\xi| \to \infty$.

2. Properties (Section 3): Linearity, shift, modulation, scaling, time reversal, differentiation, convolution-multiplication duality. The Master Properties Table encodes all relationships between time and frequency operations.

3. Inversion (Section 4): Under sufficient conditions, $f(t) = \int\hat{f}(\xi)e^{2\pi i\xi t}\,d\xi$. The Gauss-Weierstrass regularization gives a constructive proof.

4. Plancherel (Section 5): $\lVert\hat{f}\rVert_2 = \lVert f\rVert_2$. The FT is a unitary isometry on $L^2(\mathbb{R})$ - energy is preserved.

5. Uncertainty Principle (Section 6): $\Delta t\cdot\Delta\xi \geq 1/(4\pi)$, with equality iff $f$ is a Gaussian. Time-frequency concentration is fundamentally limited.

6. Distribution extension (Section 7): The FT extends to tempered distributions, giving $\mathcal{F}[\delta] = 1$, $\mathcal{F}[1] = \delta$, $\mathcal{F}[e^{2\pi i\xi_0 t}] = \delta(\xi-\xi_0)$, and the Dirac comb formula. Poisson summation unifies Fourier series and Fourier Transform.

These six results form a complete, self-consistent theory that has shaped mathematics, physics, engineering, and AI for two centuries - and shows no sign of becoming less central.

---

Appendix D: Machine Learning Deep Dives

D.1 FNet Architecture - Full Mathematical Analysis

We give a complete mathematical analysis of the FNet architecture (Lee-Thorp et al., 2022) using the formalism developed in this section.

Standard Transformer token mixing (attention):

Given token matrix $X \in \mathbb{R}^{N \times d}$ (sequence length $N$, embedding dimension $d$):

$$\text{Attn}(X) = \operatorname{softmax}\!\left(\frac{XW_Q W_K^\top X^\top}{\sqrt{d_k}}\right)XW_V$$

This is $O(N^2 d_k)$ in memory and time (the $N \times N$ attention matrix dominates for large $N$). The attention matrix $A_{ij} = \operatorname{softmax}(\text{score})_{ij}$ is data-dependent: each row is a different weighted sum of the value vectors, where the weights depend on the specific input.

FNet token mixing:

$$\text{FNetMix}(X) = \operatorname{Re}(\mathcal{F}_\text{seq}[\mathcal{F}_\text{model}[X]])$$

where $\mathcal{F}_\text{seq}$ applies the DFT along the sequence dimension (rows) and $\mathcal{F}_\text{model}$ along the embedding dimension (columns).

The DFT as a matrix multiplication:

The 1D DFT can be written as $\hat{\mathbf{x}} = F\mathbf{x}$ where $F \in \mathbb{C}^{N \times N}$ with $F_{kn} = e^{-2\pi ikn/N}/\sqrt{N}$ (unitary DFT matrix). The 2D FNet mixing is:

$$\text{FNetMix}(X) = \operatorname{Re}(F_N X F_d^\top)$$

where $F_N \in \mathbb{C}^{N\times N}$ and $F_d \in \mathbb{C}^{d\times d}$ are DFT matrices.

Key properties:

1. Unitarity: $F_N F_N^* = I_N$ and $F_d F_d^* = I_d$. The FNet mixing is an isometry (before taking real part): $\lVert F_N X F_d^\top\rVert_F = \lVert X\rVert_F$ by Plancherel.

2. Global mixing: Each output position $Y_{kj} = \sum_n\sum_m X_{nm}(F_N)_{kn}(F_d)_{jm}$ depends on all $N \times d$ input values. FNet is a global mixer - exactly like attention.

3. No parameters: Unlike attention, FNet has zero parameters in the mixing layer ($F_N$ and $F_d$ are fixed). All learning happens in the feed-forward network after mixing.

4. Complexity: $O(Nd\log(Nd))$ via 2D FFT, vs $O(N^2 d)$ for attention. For $N = 512$, $d = 768$: FNet is $\sim 500\times$ fewer operations in the mixing layer.

Why taking real part? The DFT output is complex even for real inputs. Taking $\operatorname{Re}(\cdot)$ projects back to real numbers (required since the subsequent feed-forward layers expect real inputs). This discards the imaginary part - half the phase information. This is one reason FNet is weaker than attention: it cannot separately process magnitude and phase information.

Theoretical analysis: The FNet paper shows that attention with random (untrained) weights performs similarly to FNet. This suggests the attention mechanism's power comes primarily from its (trained) data-dependent mixing, not merely from being a global mixer. FNet is the "global but data-independent" baseline.

When to use FNet vs Attention:

D.2 Random Fourier Features - Implementation Details

Setup for RBF kernel: $k(\mathbf{x},\mathbf{y}) = e^{-\gamma\lVert\mathbf{x}-\mathbf{y}\rVert^2}$.

The spectral density is $p(\boldsymbol{\omega}) = \left(\frac{1}{2\pi/(2\gamma)}\right)^{d/2}e^{-\lVert\boldsymbol{\omega}\rVert^2/(4\gamma)} = \mathcal{N}(\mathbf{0}, 2\gamma I)$.

(With $\gamma = 1/2$: $p(\boldsymbol{\omega}) = \mathcal{N}(\mathbf{0}, I)$, which is the standard form.)

Feature map construction (two variants):

Random Fourier Features (RFF): Sample $\boldsymbol{\omega}_j \sim p$, $b_j \sim \mathcal{U}[0,2\pi]$:

$$\phi(\mathbf{x}) = \sqrt{2/D}\,[\cos(\boldsymbol{\omega}_1^\top\mathbf{x}+b_1),\ldots,\cos(\boldsymbol{\omega}_D^\top\mathbf{x}+b_D)]$$

Random Fourier Features (paired, no bias): Sample $\boldsymbol{\omega}_j \sim p$:

$$\phi(\mathbf{x}) = \frac{1}{\sqrt{D}}[\cos(\boldsymbol{\omega}_1^\top\mathbf{x}),\sin(\boldsymbol{\omega}_1^\top\mathbf{x}),\ldots,\cos(\boldsymbol{\omega}_D^\top\mathbf{x}),\sin(\boldsymbol{\omega}_D^\top\mathbf{x})]$$

Both give $\mathbb{E}[\phi(\mathbf{x})^\top\phi(\mathbf{y})] = k(\mathbf{x},\mathbf{y})$. The paired version has slightly lower variance.

Concentration bound:

$$P\!\left(\sup_{\mathbf{x},\mathbf{y}}\left|\phi(\mathbf{x})^\top\phi(\mathbf{y}) - k(\mathbf{x},\mathbf{y})\right| > \epsilon\right) \leq 2^8\left(\frac{\sigma_p R}{\epsilon}\right)^2 e^{-D\epsilon^2/8}$$

where $\sigma_p = \sqrt{\mathbb{E}_p[\lVert\boldsymbol{\omega}\rVert^2]}$ and $R = \max_i\lVert\mathbf{x}^{(i)}\rVert$.

Variance reduction via Quasi-Monte Carlo: Instead of random $\boldsymbol{\omega}_j$, use quasi-random sequences (Sobol, Halton) to improve coverage of frequency space. Gives $O(D^{-1}\log^d D)$ error vs $O(D^{-1/2})$ for random - significant improvement in practice.

Orthogonal Random Features (ORF) (Yu et al., 2016): Sample $\boldsymbol{\omega}_j$ as rows of $G = \frac{1}{\sqrt{D}}HDS$ where $H$ is a Hadamard matrix, $D$ is diagonal $\pm1$, $S$ is a diagonal scaling. This gives:

• Same unbiasedness: $\mathbb{E}[\phi(\mathbf{x})^\top\phi(\mathbf{y})] = k(\mathbf{x},\mathbf{y})$
• Lower variance: $O(1/D)$ vs $O(1/D)$ but with better constants
• Faster computation: $O(D\log D)$ using fast Hadamard transform

Connection to Performer: The Performer attention (Choromanski et al., 2021) approximates $\exp(q^\top k/\sqrt{d})$ (the unnormalized attention softmax kernel) using orthogonal random features:

$$\text{softmax}(q^\top k/\sqrt{d}) \approx \phi(q)^\top\phi(k), \quad \phi(\mathbf{x}) = \frac{e^{-\lVert\mathbf{x}\rVert^2/2}}{\sqrt{D}}[e^{\omega_1^\top\mathbf{x}},\ldots,e^{\omega_D^\top\mathbf{x}}]$$

This reduces attention from $O(N^2 d)$ to $O(N D d)$ - linear in sequence length $N$.

D.3 Spectral Analysis of Neural Network Weight Matrices

The spectral norm $\lVert W\rVert_2 = \sigma_{\max}(W)$ and the spectral distribution of weight matrices encode important information about the training state of a neural network.

Heavy-tailed self-regularization (Martin & Mahoney, 2021): In well-trained neural networks, the eigenvalue distribution of $W^\top W$ follows a power law: $p(\lambda) \propto \lambda^{-\alpha}$ for some $\alpha \in [2, 6]$. Under-trained or over-regularized networks have bulk (Marchenko-Pastur) distributions. This is detected by fitting a power law to the sorted singular values.

WeightWatcher: The open-source tool weightwatcher analyzes the spectral distribution of weight matrices in PyTorch/TensorFlow models and reports $\alpha$ values as a proxy for model quality - without needing test data. Well-trained frontier models (GPT-4, LLaMA) have $\alpha \approx 2$-4; poorly trained models have $\alpha > 6$ or non-power-law distributions.

Spectral norm and Lipschitz constant: For a multi-layer network $f = f_L\circ\cdots\circ f_1$, the Lipschitz constant satisfies:

$$\text{Lip}(f) \leq \prod_{l=1}^L\lVert W^{[l]}\rVert_2\cdot\text{Lip}(\sigma)$$

For 1-Lipschitz activations ($\sigma = \operatorname{ReLU}$, $\text{Lip}(\sigma) = 1$): $\text{Lip}(f) \leq \prod_l\lVert W^{[l]}\rVert_2$.

Spectral normalization (Section 8.3) sets each $\lVert W^{[l]}\rVert_2 = 1$, making the entire network 1-Lipschitz.

For LLMs: Analyzing the spectral properties of attention weight matrices ($W_Q, W_K, W_V, W_O$) is an active area of mechanistic interpretability research. Low-rank structure in these matrices (small effective rank = few large singular values) indicates specialized computation. Anthropic's interpretability work has found "singular value signatures" of specific computational patterns in attention heads.

D.4 The Fourier Perspective on Attention

Attention and the Fourier Transform are both global linear mixing operations on sequences. Understanding their relationship clarifies when each is appropriate.

Attention as a data-dependent filter: The output of attention can be written as:

$$y_i = \sum_j A_{ij}v_j, \quad A_{ij} = \frac{\exp(q_i^\top k_j/\sqrt{d_k})}{\sum_\ell\exp(q_i^\top k_\ell/\sqrt{d_k})}$$

For fixed query $i$, this is a weighted average of value vectors with data-dependent weights $A_{ij}$. In signal processing terms, it is a position-dependent filter: the filter coefficients $A_{ij}$ change for each output position $i$.

Fourier Transform as a fixed filter bank: FNet applies the DFT, which is a fixed (non-data-dependent) filter: the output at frequency $k$ is always $\hat{x}_k = \sum_n x_n e^{-2\pi ikn/N}$, regardless of the content of $x$. Each DFT frequency is a specific pattern of oscillation at rate $k/N$.

Comparison table:

The analogy: Attention is like a learnable short-time Fourier Transform with adaptive windows - for each output position, it selects which "frequencies" (patterns) to attend to. The DFT in FNet is like a fixed global frequency analysis with no adaptivity. The power of attention comes from its ability to compute different effective filters for different positions and different inputs.

---

Appendix E: Reference Summary and Quick Checks

E.1 The Six Most Important Facts

If you retain only six things from this section, retain these:

1. Definition: $\hat{f}(\xi) = \int_{-\infty}^\infty f(t)e^{-2\pi i\xi t}\,dt$ (use the $\xi$-convention; no $2\pi$ in the inverse).

2. Self-dual Gaussian: $\mathcal{F}[e^{-\pi t^2}](\xi) = e^{-\pi\xi^2}$. The Gaussian maps to itself. All other transforms can be derived from this one via properties.

3. Plancherel: $\lVert\hat{f}\rVert_2 = \lVert f\rVert_2$. Energy is conserved. The FT is a unitary operator on $L^2$.

4. Uncertainty principle: $\Delta t\cdot\Delta\xi \geq 1/(4\pi)$, equality iff Gaussian. You cannot have both time and frequency concentration.

5. Distributions: $\mathcal{F}[\delta] = 1$, $\mathcal{F}[1] = \delta$, $\mathcal{F}[e^{2\pi i\xi_0 t}] = \delta(\xi-\xi_0)$. Pure tones map to spikes. Spikes have flat spectra.

6. AI: The FT is used in RoPE (modulation theorem), FNet (global mixing via DFT), RFF (Bochner + spectral sampling), spectral normalization (spectral norm of weight matrices), and FNO (learn in Fourier space).

E.2 Quick Reference: Which Theorem to Use When

E.3 Sign Convention Reference

Different sources use different sign conventions. This table gives the conversion formulas.

Conversion: If $F_\xi(\xi)$ is the transform in the $\xi$-convention, then $F_\omega(\omega) = F_\xi(\omega/(2\pi))$ for the non-symmetric $\omega$-convention.

Properties in the $\omega$-convention (no $1/(2\pi)$):

• Differentiation: $\mathcal{F}_\omega[f'](\omega) = i\omega F(\omega)$ (not $2\pi i\xi$)
• Time-shift: $\mathcal{F}_\omega[f(t-a)](\omega) = e^{-i\omega a}F(\omega)$ (not $e^{-2\pi i\xi a}$)
• Parseval: $\int|f|^2 = \frac{1}{2\pi}\int|F|^2$ (extra $1/(2\pi)$ factor!)

The $\xi$-convention is self-symmetric and avoids all these $2\pi$ factors - strongly recommended for all new work.

E.4 Prerequisites Revisited: What You Now Know

This section assumed you knew Fourier series (Section 01) and functional analysis basics. Here is what each prerequisite contributed:

E.5 Glossary

---

Appendix F: The Fourier Transform in Practice - Case Studies

F.1 Case Study: Audio Preprocessing for Whisper

OpenAI's Whisper (Radford et al., 2022) is a speech recognition model that accepts raw audio and produces text. Its preprocessing pipeline is a direct application of STFT and spectral analysis.

Step 1: Resampling. Raw audio is resampled to 16kHz. By Shannon's sampling theorem (Poisson summation): a signal sampled at 16kHz can faithfully represent frequencies up to 8kHz - which covers all speech frequencies (human voice: 80Hz-8kHz, formants: 200Hz-4kHz).

Step 2: STFT. Apply a windowed Fourier Transform with:

• Window: Hann window (smooth tapering reduces spectral leakage)
• Window length: 25ms 16kHz = 400 samples
• Hop length: 10ms 16kHz = 160 samples (75% overlap)
• FFT size: 512 points (zero-padded for frequency resolution)

This gives a spectrogram of shape $(\text{frames} \times 257)$ where 257 = 512/2 + 1 unique frequencies.

Step 3: Mel filterbank. Map the 257 linear frequencies to 80 mel-scale frequency bins using triangular filters. The mel scale $m = 2595\log_{10}(1 + f/700)$ is perceptually uniform - equal mel intervals are equally distinguishable to humans. The uncertainty principle is no longer limiting here because the window (25ms) is longer than the smallest perceptible phoneme duration (~10-20ms), so time resolution is slightly sacrificed for good frequency resolution.

Step 4: Log compression. Take $\log(\max(\text{mel spectrogram}, 10^{-10}))$. The log operation compresses the dynamic range of audio energy (from ~120 dB to ~12 dB).

Result: $(\text{frames} \times 80)$ log-mel spectrogram, treated as a 2D "image" and fed to a CNN + Transformer encoder. The entire preprocessing is fixed (not learned) - it embeds centuries of signal processing knowledge into the model architecture.

Fourier analysis used:

• Fourier Transform -> STFT window analysis
• Uncertainty principle -> window length tradeoff
• Sampling theorem -> 16kHz minimum rate
• Spectral leakage -> Hann window choice

F.2 Case Study: LLaMA-3 Context Extension via RoPE Scaling

LLaMA-3 uses RoPE with base $\theta_{\text{base}} = 500{,}000$ and supports up to 128K token context (compared to LLaMA-2's 4K with $\theta_{\text{base}} = 10{,}000$).

The problem: Standard RoPE with $\theta_j = 10000^{-2j/d}$ has frequencies ranging from $\theta_0 = 1$ (dimension pair 0) to $\theta_{d/2-1} = 10^{-4}$ (last dimension pair). At frequency $\theta_j$, the RoPE encoding completes one full rotation (period = $2\pi/\theta_j$ tokens). The maximum distinguishable context is the longest period: $T_{\max} = 2\pi/\theta_{\min} = 2\pi\times 10^4 \approx 62{,}832$ tokens for $d = 4096$ - explaining why LLaMA-2 degrades beyond ~4K (it uses $\theta_{\text{base}} = 10000$, so the longest period is $2\pi\times 10^4/d$... the exact computation depends on $d$).

The Fourier interpretation: Each dimension pair is an oscillator at frequency $\theta_j$. For two positions $m$ and $n$ to be distinguishable, their phase difference $|(m-n)\theta_j|$ must be $\neq 0$ mod $2\pi$ for at least one $j$. If $|m-n|$ is larger than $2\pi/\theta_{\min}$, all dimensions have wrapped around - positions become identical. This is aliasing in the temporal domain, caused by the frequency $\theta_{\min}$ being too high.

The fix: Reduce the minimum frequency by increasing $\theta_{\text{base}}$:

$$\theta_j = \theta_{\text{base}}^{-2j/d}, \quad \theta_{\min} = \theta_{\text{base}}^{-1}, \quad T_{\max} = 2\pi\cdot\theta_{\text{base}}$$

LLaMA-3 uses $\theta_{\text{base}} = 500{,}000$, giving $T_{\max} = 2\pi\times 500{,}000 \approx 3.14\times 10^6$ - more than enough for 128K context.

The cost: Higher $\theta_{\text{base}}$ means the low-frequency dimensions ($j$ large) oscillate very slowly, providing little positional information for short contexts. There is a fundamental tradeoff between context length and short-range positional precision - a manifestation of the uncertainty principle in the discrete position domain.

YaRN (Peng et al., 2023): Instead of uniformly rescaling all frequencies, YaRN uses a non-uniform rescaling: high-frequency dimensions (small $j$) are scaled minimally (they handle short-range position fine), while low-frequency dimensions (large $j$) are scaled aggressively. The interpolation factor $s = \text{target context} / \text{original context}$ is applied per-frequency, weighted by the "needed" extension. This maintains short-range precision while extending long-range capacity - a principled application of the time-frequency tradeoff.

F.3 Case Study: Spectral Normalization in Stable Diffusion

Modern diffusion models (Stable Diffusion, DALL-E 3, Flux) train a discriminator or guidance network to distinguish real from generated data. Spectral normalization (Section 8.3) is used to stabilize this training.

Setup: The discriminator $D: \mathbb{R}^{H\times W\times 3} \to [0,1]$ has $L$ convolutional layers. Each convolution layer has weight $W^{[l]} \in \mathbb{R}^{C_\text{out}\times C_\text{in}\times k\times k}$. For a 2D convolution layer, the relevant spectral norm is:

$$\lVert W^{[l]}\rVert_2 = \max_{\mathbf{h}:\lVert\mathbf{h}\rVert=1}\lVert W^{[l]}*\mathbf{h}\rVert$$

For a convolution with kernel $h(k_x, k_y)$, the spectral norm equals $\max_{\xi_x,\xi_y}|\hat{h}(\xi_x,\xi_y)|$ - the maximum of the 2D Fourier Transform of the kernel. This connects spectral normalization directly to the FT: normalizing by the spectral norm makes the filter's frequency response bounded by 1 at every frequency.

Effect on generated images: A spectrally-normalized discriminator applies Lipschitz constraints that prevent it from exploiting arbitrary high-frequency artifacts in generated images. This forces the generator to eliminate high-frequency artifacts (checkerboard patterns from transposed convolutions, aliasing from bilinear upsampling) - improving sample quality.

Alias-free GAN / StyleGAN3 (Karras et al., 2021): Takes spectral control further by enforcing alias-free processing throughout the generator using carefully designed low-pass filters at every upsampling step. The key insight from Fourier analysis: any nonlinearity applied to a bandlimited signal creates harmonics beyond the original bandwidth - these must be filtered out before downsampling to avoid aliasing. StyleGAN3's architecture enforces this principle throughout, producing significantly more temporally consistent video outputs.

---