Fourier Analysis - Series, Transforms, and Signal Processing

Table of Contents

1. Fourier Series
2. Fourier Transform
3. Discrete Fourier Transform
4. Fast Fourier Transform
5. Convolution
6. Applications
7. Wavelets

---

Fourier Series

Periodic Functions

$f$ periodic with period $T$: $f(x + T) = f(x)$ for all $x$

Fundamental period: Smallest $T > 0$

Functions with period $2\pi$:

$f(x) \sim \frac{a_0}{2} + \sum_{n=1}^{\infty} [a_n \cos(nx) + b_n \sin(nx)]$

Coefficients

$a_n$ (cosine coefficients): $a_n = \frac{1}{\pi} \int_0^{2\pi} f(x)\cos(nx) \, dx$

for $n = 0, 1, 2, \dots$

$b_n$ (sine coefficients): $b_n = \frac{1}{\pi} \int_0^{2\pi} f(x)\sin(nx) \, dx$

for $n = 1, 2, \dots$

Parseval’s theorem: $\frac{a_0^2}{2} + \sum_{n=1}^{\infty} (a_n^2 + b_n^2) = \frac{1}{\pi} \int_0^{2\pi} [f(x)]^2 \, dx$

Complex Form

$f(x) \sim \sum c_n e^{inx}$

where $c_n = \frac{1}{2\pi} \int_0^{2\pi} f(x) e^{-inx} \, dx$

Relationship:

• $c_0 = a_0/2$
• $c_n = (a_n - ib_n)/2$
• $c_{-n} = (a_n + ib_n)/2$

General Period

$f$ with period $2L$:

$f(x) \sim \frac{a_0}{2} + \sum_{n=1}^{\infty} \left[a_n \cos\left(\frac{n\pi x}{L}\right) + b_n \sin\left(\frac{n\pi x}{L}\right)\right]$

Coefficients: $a_n = \frac{1}{L} \int_{-L}^L f(x)\cos\left(\frac{n\pi x}{L}\right) \, dx$ $b_n = \frac{1}{L} \int_{-L}^L f(x)\sin\left(\frac{n\pi x}{L}\right) \, dx$

Convergence

Pointwise convergence: If $f$ piecewise continuous: $\lim_{N \to \infty} S_N(x) = \frac{f(x^+) + f(x^-)}{2}$

where $S_N$ is $N$-th partial sum

Uniform convergence: If $f$ continuous and periodic, Fourier series converges uniformly

Gibbs Phenomenon

Overshoot near discontinuities does not vanish

Oscillations persist but area $\to 0$

---

Fourier Transform

Definition

Fourier transform: $\hat{f}(\xi) = \int_{-\infty}^{\infty} f(x) e^{-2\pi i\xi x} \, dx$

Inverse: $f(x) = \int_{-\infty}^{\infty} \hat{f}(\xi) e^{2\pi i\xi x} \, d\xi$

Alternative convention: $\hat{f}(\omega) = \int_{-\infty}^{\infty} f(x) e^{-i\omega x} \, dx$

with factor $1/(2\pi)$ in inverse

Properties

Linearity: $\widehat{af + bg}(\xi) = a\hat{f}(\xi) + b\hat{g}(\xi)$

Shift: $\widehat{f(x-a)}(\xi) = e^{-2\pi ia\xi} \hat{f}(\xi)$

Modulation: $\widehat{f(x) e^{2\pi iax}}(\xi) = \hat{f}(\xi - a)$

Scaling: $\widehat{f(ax)}(\xi) = \frac{1}{|a|} \hat{f}\left(\frac{\xi}{a}\right)$

Derivative: $\widehat{f'(x)}(\xi) = 2\pi i\xi \hat{f}(\xi)$

Multiplication by x: $\widehat{xf(x)}(\xi) = \frac{i}{2\pi} \hat{f}'(\xi)$

Convolution Theorem

$\widehat{f * g}(\xi) = \hat{f}(\xi) \hat{g}(\xi)$

Product: $\widehat{fg}(\xi) = (\hat{f} * \hat{g})(\xi)$

Parseval’s Theorem

$\int_{-\infty}^{\infty} |f(x)|^2 \, dx = \int_{-\infty}^{\infty} |\hat{f}(\xi)|^2 \, d\xi$

Energy conservation

Common Transforms

Gaussian: $f(x) = e^{-ax^2}$ $\hat{f}(\xi) = \sqrt{\frac{\pi}{a}} e^{-\pi^2\xi^2/a}$

Rectangular pulse: $f(x) = 1$ for $|x| \leq a$, else 0 $\hat{f}(\xi) = \frac{\sin(2\pi a\xi)}{\pi\xi}$

Exponential decay: $f(x) = e^{-a|x|}$ $\hat{f}(\xi) = \frac{2a}{a^2 + 4\pi^2\xi^2}$

Uncertainty Principle

Heisenberg uncertainty: $\Delta x \cdot \Delta \xi \geq \frac{1}{4\pi}$

Cannot localize both in space and frequency simultaneously

---

Discrete Fourier Transform

Definition

For sequence $x[n], n = 0, \dots, N-1$:

$X[k] = \sum_{n=0}^{N-1} x[n] e^{-2\pi ikn/N}$

Inverse DFT: $x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{2\pi ikn/N}$

Periodic: $X[k + N] = X[k], x[n + N] = x[n]$

Properties

Circular shift:

$\text{DFT}\{x[n-m]\} = e^{-2\pi ikm/N} X[k]$

Convolution (circular):

$\text{DFT}\{x[n] \circledast y[n]\} = X[k] Y[k]$

Parseval: $\sum_{n=0}^{N-1} |x[n]|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |X[k]|^2$

Zero-Padding

Add zeros to extend sequence

Interpolates spectrum

Useful for increased frequency resolution

---

Fast Fourier Transform

Computational Complexity

Naive DFT: $O(N^2)$ operations

FFT: $O(N \log N)$ operations

Radix-2 FFT: $N$ is power of 2

Decimation-in-Time (DIT): Divide into even and odd subsequences

Recursive: $FFT(N) = 2 FFT(N/2) + O(N)$

Twiddle factors: $W_N^{kn} = e^{-2\pi ikn/N}$

Cooley-Tukey Algorithm

For $N = 2^m$:

Recursively compute FFTs of half-size, combine

Butterfly operation: Sum and difference with twiddle factor

Practical Considerations

Window functions: Reduce spectral leakage

Blackman-Harris: Suppresses side lobes

Zero-padding: Increase frequency resolution without interpolation

---

Convolution

Continuous Convolution

$(f * g)(x) = \int f(y)g(x-y) dy$

Properties:

• Commutative: $f * g = g * f$
• Associative: $(f * g) * h = f * (g * h)$
• Distributive: $f * (g + h) = f * g + f * h$

Unit impulse $\delta(x)$: $f * \delta = f$

Fourier transform: $\widehat{f * g} = \hat{f} \hat{g}$

Discrete Convolution

$(x * y)[n] = \sum x[k]y[n-k]$

Circular convolution (periodic): $(x \circledast y)[n] = \sum x[k]y[(n-k) \mod N]$

Linear convolution via DFT: Zero-pad both sequences to length $\geq M + N - 1$

---

Applications

Signal Processing

Filtering: Multiply in frequency domain

Noise reduction: Remove high-frequency components

Compression: Quantize Fourier coefficients

Image Processing

2D Fourier transform: $F(u,v) = \iint f(x,y)e^{-2\pi i(ux+vy)} dx dy$

Filtering: Blur, sharpen, edge detection

Pattern recognition: Correlation

Partial Differential Equations

Heat equation: $u_t = k\nabla^2 u$

Take Fourier transform: $\hat{u}_t = -k(2\pi\xi)^2\hat{u}$

Solution: $\hat{u}(\xi,t) = \hat{u}(\xi,0)e^{-k(2\pi\xi)^2t}$

Inverse: Convolution with heat kernel

Wave equation: $u_{tt} = c^2\nabla^2 u$

Dispersion relation: $\omega = c|k|$

---

Wavelets

Short-Time Fourier Transform

STFT: Windowed Fourier transform

$STFT[f](t,ξ) = \int f(τ)w(τ-t)e^{-iξτ} dτ$

Time-frequency resolution: Trade-off (uncertainty principle)

Wavelet Transform

Continuous wavelet transform:

$WT[f](a,b) = \frac{1}{\sqrt{a}} \int f(t) \psi\left(\frac{t-b}{a}\right) dt$

a: scale, b: translation

Multiresolution analysis: Different scales

Mother wavelet $\psi(t)$: Oscillates, decays

Haar Wavelets

Simplest example:

Scaling function: $\phi(x) = 1$ for $0 \leq x \leq 1$, else 0

Wavelet: $\psi(x) = 1$ for $0 \leq x < 1/2, -1$ for $1/2 \leq x < 1$

Orthonormal basis at each resolution level

Applications

Data compression: JPEG 2000

Signal denoising: Threshold small coefficients

Image processing: Multiresolution features

Compressed sensing: Random sampling with structure

---

Next: Tensor Analysis

---

Last updated: Comprehensive Fourier analysis reference covering series, transforms, and wavelets.