Fourier Analysis: Decomposing Signals into Frequencies

1. Fourier Series

A Fourier series represents a periodic function as a superposition of sinusoidal waves. The fundamental idea — that any periodic signal can be built from harmonics — was revolutionary when Fourier proposed it in 1807 and remains central to analysis today.

Definition and Coefficients

Let f be a real-valued function with period 2*pi (or period L with appropriate scaling). The Fourier series of f is:

The coefficient a_0/2 is the mean value of f over one period. The coefficients a_n and b_n measure how much of the n-th harmonic cos(n*x) and sin(n*x) is present in f. Using complex exponentials simplifies the formulas: the complex Fourier coefficient is c_n = (1/2*pi) * integral from -pi to pi of f(x)*exp(-i*n*x) dx, and f(x) = sum over n from -infinity to +infinity of c_n*exp(i*n*x).

Orthogonality

The trigonometric system is orthogonal on [-pi, pi]. This means:

Orthogonality is why projecting f onto each basis function (integrating against cos(n*x) or sin(n*x)) isolates exactly the n-th coefficient. The trigonometric system forms a complete orthonormal basis for L^2([-pi, pi]) after normalization.

Parseval's Identity

Parseval's identity is the Fourier series analogue of the Pythagorean theorem. For f in L^2([-pi, pi]):

This says the total energy of f equals the sum of energies of its Fourier coefficients. Parseval's identity also implies that if all Fourier coefficients of f are zero, then f = 0 in L^2, confirming completeness of the trigonometric system.

Convergence: Dirichlet Conditions

The Dirichlet theorem gives sufficient conditions for pointwise convergence of a Fourier series:

• →f is periodic with period 2*pi
• →f has finitely many jump discontinuities in [-pi, pi]
• →f has finitely many local maxima and minima in [-pi, pi]

Under these conditions, the Fourier series converges to f(x) at every continuity point, and to (f(x-) + f(x+))/2 — the average of left and right limits — at each jump discontinuity.

Gibbs Phenomenon

2. The Fourier Transform

The Fourier transform extends Fourier series to non-periodic functions on the real line. Instead of discrete frequencies n = 0, 1, 2, ..., it produces a continuous spectrum over all real frequencies xi.

Definition

For f in L^1(R), the Fourier transform is:

Alternative conventions place 2*pi in the exponent differently or include a factor of 1/sqrt(2*pi). The convention above is most common in engineering and probability. The angular frequency convention uses omega = 2*pi*xi and writes exp(-i*omega*x).

Key Properties

The differentiation property is especially powerful: it converts differential equations into algebraic equations in the frequency domain, because differentiation in time becomes multiplication by the frequency variable.

Inversion Formula

The Fourier inversion theorem states: if f is in L^1(R) and its transform f-hat is also in L^1(R), then for almost every x,

3. Fourier Transform on L^1 and L^2

The rigorous theory of the Fourier transform requires careful attention to which function spaces it acts on. The behavior differs significantly between L^1 and L^2.

Riemann-Lebesgue Lemma

For any f in L^1(R), its Fourier transform satisfies:

Plancherel Theorem (Extension to L^2)

The Plancherel theorem is the cornerstone of L^2 Fourier theory:

Because the Fourier transform preserves the L^2 norm, it extends uniquely from L^1 intersection L^2 to all of L^2(R) as a unitary (norm-preserving) isometry. The image of the Fourier transform on L^2 is all of L^2 — it is surjective. This makes the L^2 Fourier transform a unitary operator on the Hilbert space L^2(R), and its inverse equals its adjoint.

Schwartz Space and Tempered Distributions

The Schwartz space S(R) consists of all infinitely differentiable functions that decay rapidly at infinity:

The Fourier transform maps S(R) to S(R) bijectively — it is a topological automorphism of Schwartz space. This is the ideal setting: the transform and its inverse are both defined and map nice functions to nice functions.

Tempered distributions are continuous linear functionals on S(R). The Fourier transform extends to tempered distributions by duality: for a tempered distribution T and a Schwartz function phi, define F(T)(phi) = T(F(phi)). This allows the Fourier transform of the Dirac delta and other singular objects to be defined rigorously.

Dirac Delta and Weak Derivatives

The Dirac delta delta(x) is not a function but a distribution: delta(phi) = phi(0) for all phi in S(R). Its Fourier transform is:

These identities make rigorous the informal idea that a pure sinusoid is concentrated at a single frequency. The weak derivative of a distribution T is defined by D(T)(phi) = -T(D(phi)), extending differentiation to functions like the Heaviside step function whose classical derivative does not exist. The weak derivative of the Heaviside function is the Dirac delta.

4. Discrete Fourier Transform (DFT)

The DFT operates on finite sequences of complex numbers rather than continuous functions. It is the version implemented in computers and the foundation of all practical spectral analysis.

Definition

Given a sequence x_0, x_1, ..., x(N-1) of N complex numbers, the DFT produces N frequency-domain values X_0, X_1, ..., X(N-1):

Matrix Form

The DFT is a linear transformation, so it can be written as matrix multiplication X = W * x, where W is the N x N DFT matrix with entries W(k,n) = omega^(k*n) and omega = exp(-2*pi*i/N) (the primitive N-th root of unity):

Cyclic Convolution

The DFT converts cyclic (circular) convolution into pointwise multiplication. Given two sequences x and h of length N, their cyclic convolution y is:

To compute linear convolution (not cyclic) using the DFT, zero-pad both sequences to length at least M + N - 1 (where M, N are the original lengths), compute the DFT of each, multiply pointwise, then take the inverse DFT. This exploits the FFT's O(N log N) speed rather than direct O(N^2) convolution.

DFT Properties and Applications

• →Periodicity: X_k = X(k+N), so the spectrum is periodic with period N
• →Parseval: sum of |x_n|^2 = (1/N) * sum of |X_k|^2 (energy conservation)
• →For real inputs, X(N-k) = X_k-bar (conjugate symmetry), so only the first N/2 + 1 values are independent
• →Applications: spectral analysis, digital filtering, solving difference equations, data compression, MRI reconstruction

5. Fast Fourier Transform (FFT)

The Fast Fourier Transform is an algorithm — not a different mathematical transform — that computes the DFT in O(N log N) time instead of O(N^2). The Cooley-Tukey algorithm (1965) is the most widely used FFT, though related ideas appeared in Gauss's work around 1805.

Cooley-Tukey Radix-2 Algorithm

When N = 2^m (a power of 2), the DFT can be split into two DFTs of length N/2 using the even-odd decomposition. Let omega_N = exp(-2*pi*i/N):

The twiddle factor omega_N^k rotates the odd DFT result before combining. The key insight is that E(k+N/2) = E_k and O(k+N/2) = O_k (periodicity of the sub-DFTs), so we only need to compute N/2 values of each sub-DFT to recover all N values of the full DFT. This halving recurses: each N/2 DFT splits into two N/4 DFTs, and so on.

Complexity Analysis

For non-power-of-2 sizes, the mixed-radix FFT factors N into smaller primes and applies analogous splits. The Bluestein algorithm handles arbitrary N by embedding the DFT into a convolution computable by a power-of-2 FFT.

Bit Reversal Permutation

The recursive even-odd splitting rearranges the input in a specific permutation: the index of each element in the final rearrangement is the bit-reversal of its original index. For N = 8:

In-place iterative FFT implementations apply this bit-reversal permutation first, then perform log_2(N) butterfly passes. Each butterfly is the elementary operation that computes (a + w*b, a - w*b) from two values (a, b) and a twiddle factor w.

6. Convolution Theorem

The convolution theorem is perhaps the single most useful property of the Fourier transform in applications, converting a computationally expensive integral operation into simple multiplication.

Convolution in Time and Frequency

The convolution of two functions f and g is:

The theorem requires f and g to be in L^1(R) for the convolution theorem to hold in L^1. For L^2 functions the theorem holds with the Fourier transform interpreted in the L^2 sense. In the DFT setting, convolution becomes cyclic convolution (see Section 4).

Applications of the Convolution Theorem

7. Sampling Theory: Nyquist-Shannon Theorem

Sampling theory addresses the fundamental question: how densely must we sample a continuous signal to capture all its information, and how can we perfectly reconstruct it from those samples?

Bandlimited Signals

A function f is bandlimited to B Hz if its Fourier transform f-hat(xi) = 0 for all |xi| greater than B. This means f contains no frequency components above B. Examples include audio signals processed through a low-pass filter.

Nyquist-Shannon Sampling Theorem

The sinc function is the ideal interpolation kernel. Each sample f(n/T) contributes a shifted sinc, and the sum reconstructs f exactly. In practice, sinc has infinite support so perfect reconstruction requires infinitely many samples — practical systems use truncated or windowed sinc approximations.

Aliasing

If f is sampled at rate T less than 2B (below Nyquist), frequency components above T/2 fold back (alias) into the baseband [0, T/2]. The spectrum of the sampled signal is the sum of shifted copies of f-hat, spaced T apart; when T is too small these copies overlap, corrupting the spectrum irreversibly.

Oversampling and Interpolation

Sampling at a rate far above Nyquist (oversampling) provides immunity to aliasing and simplifies anti-aliasing filter design. Modern audio codecs typically oversample by factors of 64-128x, apply digital filtering, then downsample. Interpolation between samples uses polynomial methods (linear, cubic spline, Lanczos) as practical approximations to sinc interpolation.

8. Short-Time Fourier Transform and Time-Frequency Analysis

The global Fourier transform reveals which frequencies are present in a signal but not when they occur. The short-time Fourier transform (STFT) provides local frequency information by analyzing the signal through a sliding window.

Definition of the STFT

Given a window function g (typically a Gaussian or Hann window), the STFT of f is:

The window g(x - t) localizes the analysis near time t. The result STFT(f)(t, xi) tells us roughly how much of frequency xi is present near time t. The magnitude squared |STFT(f)(t, xi)|^2 is the spectrogram, used in speech processing, music analysis, and audio recognition.

The Heisenberg-Gabor Uncertainty Principle

A fundamental limitation: no signal can be perfectly localized in both time and frequency simultaneously. The time-bandwidth product is bounded below:

Gabor atoms are Gaussians modulated by sinusoids: g(t) = exp(-pi*t^2) * exp(2*pi*i*xi_0*t). They achieve the uncertainty bound and form the basis of Gabor analysis. The Wigner-Ville distribution is an alternative time-frequency representation with better theoretical properties but cross-term interference artifacts.

9. Wavelets and Multiresolution Analysis

Wavelets overcome the fixed time-frequency trade-off of the STFT by using short windows at high frequencies and long windows at low frequencies — adapting resolution to the signal scale.

Continuous Wavelet Transform (CWT)

The CWT analyzes f at scale a (dilation) and position b (translation) using a mother wavelet psi:

The admissibility condition for psi requires that the integral of psi over all t is zero (psi has zero mean) and that integral of |psi-hat(xi)|^2 / |xi| d*xi is finite. Under admissibility, the reconstruction formula holds:

Multiresolution Analysis (MRA)

MRA provides the algebraic framework for the discrete wavelet transform. An MRA consists of a nested sequence of closed subspaces of L^2(R):

At each level j, V_j approximates L^2 functions at resolution 2^j. The detail space W_j is the orthogonal complement of V_j in V(j+1): V(j+1) = V_j plus W_j. Wavelets psi(j,k) = 2^(j/2) * psi(2^j*x - k) form an orthonormal basis for W_j. Together, all wavelet spaces give a complete orthonormal basis for L^2(R).

Haar Wavelet

The simplest wavelet, proposed by Haar in 1910:

The corresponding scaling function phi(t) = 1 on [0, 1), 0 elsewhere (the box function). Haar wavelets have compact support (which is good for localization) but are discontinuous (which limits regularity in applications). The Haar DWT of a sequence proceeds by averaging and differencing adjacent pairs.

Daubechies Wavelets

Daubechies (1988) constructed compactly supported orthogonal wavelets with higher regularity. The Daubechies-N (DbN) wavelet has N vanishing moments (integral of t^k * psi(t) dt = 0 for k = 0, ..., N-1) and support of length 2N - 1. Key examples:

• →Db1 = Haar wavelet (1 vanishing moment, support length 1)
• →Db2 (1 vanishing moment beyond Haar, support length 3, continuous)
• →Db4 (4 vanishing moments, support length 7, used in JPEG 2000)
• →More vanishing moments = better polynomial approximation = better compression, but longer filters = more computation

Discrete Wavelet Transform (DWT)

The DWT decomposes a signal x into approximation coefficients (low frequency) and detail coefficients (high frequency) at each scale using a pair of filters: low-pass h and high-pass g derived from the scaling function and wavelet. One level of the DWT:

This filter bank structure makes the DWT efficient: one level of DWT costs O(N). The approximation a_j is recursively decomposed, giving a logarithmic tree of coefficients. The full multi-level DWT costs O(N) total. Perfect reconstruction is guaranteed by the quadrature mirror filter (QMF) conditions on h and g.

10. Applications to Partial Differential Equations

The Fourier transform is one of the most powerful tools for solving PDEs, converting differential equations in x into algebraic equations in the frequency variable xi, which can be solved explicitly.

Heat Equation on the Real Line

The heat equation describes temperature evolution u(x, t):

The solution is the convolution of the initial data f with the heat kernel G_t. Differentiating in the frequency domain became multiplication, turning the PDE into an ODE that is trivial to solve.

Wave Equation

The 1D wave equation u_tt = c^2 * u_xx with initial conditions u(x, 0) = f(x) and u_t(x, 0) = g(x) transforms to:

Poisson Equation

The Poisson equation in R^n, minus-Laplacian u = f, transforms to:

The Fourier transform also reveals the symbol of a differential operator: the Laplacian has symbol -4*pi^2*|xi|^2. Pseudodifferential operators generalize this: instead of a polynomial in xi, the symbol can be any suitable function of xi, allowing fractional powers of the Laplacian and other non-local operators.

11. Applications in Science and Engineering

Fourier analysis is embedded in virtually every area of modern science, engineering, and data processing.

12. Practice Problems with Solutions

Work through these problems to master Fourier analysis. Click each problem to reveal the solution.

Essential Theorems at a Glance