Discrete Fourier transform

Motivation

See several coupled oscillators#Transformation to Normal Coordinates via Discrete Fourier Transform, to see it in the context of a discrete chain of oscillators.

In coupled oscillator systems, we seek to decouple the equations of motion by transforming to normal coordinates:

q (t) = V Q (t)

where:

$V$ is the matrix of eigenvectors of the system,
$Q (t)$ contains the time-dependent normal coordinates,
Each $Q_{k} (t)$ evolves independently:

{\ddot{Q}}_{k} + ω_{k}^{2} Q_{k} = 0

Key point: After the transformation, we still need to solve differential equations for the time evolution of the system, but they are simpler (decoupled).

On the other hand, in image processing, an image (e.g. a 3×3 array $f_{i, j}$ ) is static. We apply the discrete Fourier transform (DFT):

F_{u, v} = \sum_{i, j} f_{i, j} e^{- 2 π i (\frac{i u}{3} + \frac{j v}{3})}

where:

$f_{i, j}$ are the pixel values (grey levels),
$F_{u, v}$ are the frequency components.

Key point: The DFT expresses the image as a sum of spatial frequency patterns (sinusoids), but no time evolution is involved. We simply compute these coefficients once:

f_{i, j} = \frac{1}{9} \sum_{u, v} F_{u, v} e^{2 π i (\frac{i u}{3} + \frac{j v}{3})}

Nuance: The analogy with normal modes of oscillators rests on an assumed or implicit spatial coupling between neighboring pixels—similar to how springs couple oscillators. In oscillators, the normal mode basis arises from diagonalizing a specific coupling matrix (spring forces); in images, the DFT basis is meaningful because we assume or model that nearby pixel values are correlated (as if coupled), making spatial sinusoids a natural basis for decomposition. Without this assumption, applying the DFT to static data is just a mathematical choice, not one tied to any physical coupling.

Note: The Fast Fourier Transform (FFT) is a fast algorithm to compute the DFT. The mathematical meaning is the same; FFT just makes it computationally feasible.

Definition

Let $ℓ^{2} (Z_{n})$ denote the space of complex-valued functions on the finite cyclic group $Z_{n} = 0, 1, \dots, n - 1$ , (see l^p(Z_n)) endowed with the Hermitian inner product:

⟨ f, g ⟩ = \sum_{k = 0}^{n - 1} f (k) \overset{―}{g (k)} .

The standard basis of $ℓ^{2} (Z_{n})$ is given by the delta functions:

δ_{j} (k) = {\begin{cases} 1 & if k = j, \\ 0 & otherwise, \end{cases}

for $j = 0, 1, \dots, n - 1$ . Any function $f \in ℓ^{2} (Z_{n})$ can be written as:

f = \sum_{j = 0}^{n - 1} f (j) δ_{j} .

Define the Fourier basis ${χ_{k}}_{k = 0}^{n - 1}$ by:

χ_{k} (j) = \frac{1}{\sqrt{n}} e^{2 π i k j / n},

for $k = 0, 1, \dots, n - 1$ . These are orthonormal characters of the group $Z_{n}$ , forming a unitary basis for $ℓ^{2} (Z_{n})$ .

The Discrete Fourier Transform (DFT) of $f \in ℓ^{2} (Z_{n})$ consists of the coordinates of $f$ with respect to the Fourier basis:

\hat{f} (k) = ⟨ f, χ_{k} ⟩ = \frac{1}{\sqrt{n}} \sum_{j = 0}^{n - 1} f (j) e^{- 2 π i k j / n} .

Thus,

f = \sum_{k = 0}^{n - 1} \hat{f} (k) χ_{k},

and the inverse DFT recovers $f$ from its coordinates:

f (j) = \sum_{k = 0}^{n - 1} \hat{f} (k) χ_{k} (j) = \frac{1}{\sqrt{n}} \sum_{k = 0}^{n - 1} \hat{f} (k) e^{2 π i k j / n} .

Given a vector $f = (f (0), f (1), \dots, f (n - 1))^{T} \in ℓ^{2} (Z_{n})$ , and letting $\hat{f}$ be its Discrete Fourier Transform, the relation is:

\hat{f} = F f and f = F^{*} \hat{f}

The change of basis is given by:

F_{k j} = \frac{1}{\sqrt{n}} ω^{k j}, 0 \leq k, j < n

where $ω = e^{- 2 π i / n}$
For example, for $n = 4$ , $ω = e^{- 2 π i / 4} = i^{- 1} = - i$ . Then:

F = \frac{1}{2} [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & - i & - 1 & i \\ 1 & - 1 & 1 & - 1 \\ 1 & i & - 1 & - i \end{matrix}]

Related: Fourier transform.
Related: Fourier series expansion.
Related: convolution (discrete)