32  Fourier Analysis as Change of Basis

Fourier analysis provides a framework for representing functions and data in terms of frequency components. In engineering, this transformation is critical for signal processing, image compression, and solving differential equations where the Laplacian operator is diagonalized by the Fourier basis.

32.1 Discrete Fourier Transform (DFT)

NoteDefinition: DFT Matrix

Unitary matrix \(\mathbf{F} \in \fC^{n \times n}\) with entries: \[ \begin{align} F_{jk} = \frac{1}{\sqrt{n}} \omega_n^{jk}, \quad \omega_n = e^{-2\pi i/n}. \end{align} \]

  • Unitary Property: \(\mathbf{F}^* \mathbf{F} = \bI\). Orthonormal columns.

  • Inverse DFT: \(\mathbf{F}^{-1} = \mathbf{F}^*\).

NoteTheorem: Parseval’s Theorem

The DFT is an isometry: \(\|\mathbf{F}\bx\|_2 = \|\bx\|_2\). Total energy is preserved between time and frequency domains.

32.2 Convolution and Circulant Matrices

NoteDefinition: Circulant Matrix

Matrix \(\mathbf{C}\) where each row is a cyclic shift of the first column \(\bc\).

  • Diagonalization: Every circulant matrix is diagonalized by the DFT: \(\mathbf{C} = \mathbf{F}^* \text{diag}(\mathbf{F}\bc) \mathbf{F}\).

  • Eigenvalues: The eigenvalues of \(\mathbf{C}\) are the DFT coefficients of its first column.

NoteTheorem: Convolution Theorem

Circular convolution \(\bz = \bc * \bx\) is equivalent to pointwise multiplication in frequency: \[ \begin{align} \mathbf{F}(\bc * \bx) = (\mathbf{F}\bc) \odot (\mathbf{F}\bx). \end{align} \] Complexity: Reduced from \(O(n^2)\) (direct) to \(O(n \log n)\) (FFT).

32.3 The Fast Fourier Transform (FFT)

NoteTheorem: Cooley-Tukey Algorithm

Computes the DFT in \(O(n \log n)\) flops for \(n = 2^p\).

  • Mechanism: Recursively splits \(n\)-point DFT into two \(n/2\)-point DFTs (even/odd indices).

  • NumPy: Use np.fft.fft and np.fft.ifft.

Tip

Spectral Differentiation: For smooth periodic signals, differentiate by multiplying frequency components \(\hat{x}_k\) by \(ik\). Provides exponential accuracy compared to polynomial accuracy of finite differences.

32.4 Exercises

WarningExercise

  1. Write out the \(4 \times 4\) DFT matrix explicitly. Verify it is unitary.

  2. Solve the periodic Poisson equation \(-u'' = f\) via FFT. (Hint: Laplacian is circulant).

  3. Compare the speed of np.fft.fft(x) vs. F @ x for \(n=4096\).

  4. Implement spectral differentiation for \(f(x) = \sin(x)\) and check error vs. \(n\).