06 DFT Applications - Convolution, Algorithms, and Applications

Recap: The DFT as a Change of Basis

In our last lecture, we established that the Discrete Fourier Transform (DFT) is a fundamental operation in linear algebra: a change of basis.

• We move from the time domain (standard basis), where a signal is a sequence of values over time, to the frequency domain (trigonometric basis), where the signal is represented by the amplitudes and phases of its constituent frequencies.
• The vectors of this new basis are built from the N-th roots of unity and are mutually orthogonal. This orthogonality is the key to the DFT’s power and efficiency.
• This transformation allows us to “see” the hidden structure of a signal, making tasks like denoising intuitive and effective.

Today, we will uncover the deeper reasons why this basis is so special. We will explore a profound connection to linear algebra through circulant matrices, formally state the all-important Convolution Theorem, and then dive into the algorithmic magic of the Fast Fourier Transform (FFT). Finally, we will see these tools in action across a stunning range of applications, from medical imaging to audio compression.

The image perfectly illustrates this basis change. On the left, the signal is a dense vector of time-domain samples. On the right, the same signal is represented by its Fourier coefficients. This representation is sparse—only a few coefficients are large, immediately revealing the signal’s dominant frequencies.

The Deeper Connection: Why the Fourier Basis is Special

We’ve seen that the trigonometric basis is orthogonal, but its importance runs deeper. It is intrinsically linked to a fundamental operation in signal processing: shifting.

Circulant Matrices and the Shift Operation

Consider the most basic operation on a periodic signal: shifting it by one position. This is represented by the cyclic shift matrix, $S_N$. A circulant matrix, $C$, is a matrix where each row is a cyclic shift of the row above it. It is completely defined by its first column, $\mathbf{c}$.

A remarkable fact is that any circulant matrix can be expressed as a polynomial of the simple shift matrix $S_N$:

$$C=p(S_N)=c_{0}I+c_1{S}_N+c_2{S}_N^2+\cdots +c_{N-1}{S}_N^{N-1}$$

The “Master Key”: Simultaneous Diagonalization

In linear algebra, the natural basis for analyzing a matrix is its basis of eigenvectors. The key insight is that the eigenvectors of the fundamental shift matrix $S_N$ are none other than our trigonometric basis vectors.

Theorem: Simultaneous Diagonalization of Circulant Matrices

The Fourier Matrix $V$ (whose columns are the trigonometric basis vectors) diagonalizes every circulant matrix $C$.

$$C=V\cdot p(D)\cdot V^{-1}=\frac{1}{N}V\cdot p(D)\cdot V^H$$

where $D$ is the diagonal matrix of eigenvalues of $S_N$. The eigenvalues of $C$ are simply the DFT of its first column.

This is a profound result. The Fourier basis is the special, unique basis that simplifies the analysis of any process involving cyclic shifts. This is why it is the natural language of periodic signals.

The Convolution Theorem: The Engine of Signal Processing

We now arrive at the single most important property of the DFT for practical applications.

What is Convolution?

Convolution is a mathematical operation that describes how the shape of one function is modified by another. For discrete signals, it’s a “sliding dot product.”

$$c_k=(\mathbf{a}\ast \mathbf{b}{)}_k=\sum _{n=-\infty }^{\infty }{a}_n{b}_{k-n}$$

A naive implementation of this sum costs $O(N^2)$ operations, which is prohibitively slow for large signals.

Where does convolution appear? Everywhere!

• Filtering: Applying a filter (like a blur or an echo) to an audio or image signal is a convolution. The filter’s response is one vector, the signal is the other.
• Polynomial Multiplication: Multiplying two polynomials, like $(1+2x+4x^2)(3+0x+5x^2)$, is equivalent to convolving their coefficient vectors $(1,2,4)$ and $(3,0,5)$.
• Instrument Response: When a measurement device records a signal from the “cosmos,” what it outputs is a convolution of the true signal with the device’s own internal response function.

The Convolution Theorem

The DFT provides an incredible shortcut to this expensive operation by connecting it to a much cheaper one.

Theorem: The Convolution Theorem

The Discrete Fourier Transform of the cyclic convolution of two vectors is the pointwise product of their individual Discrete Fourier Transforms.

$$\text{DFT}(\mathbf{a}⊛\mathbf{b})=\text{DFT}(\mathbf{a})\odot \text{DFT}(\mathbf{b})$$

In other words: Convolution in the time domain is simple multiplication in the frequency domain.

This gives us a recipe to compute a convolution in just $O(N\log N)$ time:

1. Transform: Compute the DFT of $\mathbf{a}$ and $\mathbf{b}$ using the FFT.
2. Multiply: Multiply the resulting coefficient vectors element-by-element. This is an $O(N)$ operation.
3. Inverse Transform: Compute the inverse DFT of the product using the inverse FFT.

This procedure is the workhorse of modern digital signal processing.

The Fast Fourier Transform (FFT) Algorithm

The Convolution Theorem’s power is unlocked by the Fast Fourier Transform (FFT), an algorithm that computes the $O(N^2)$ DFT matrix-vector product in an astonishing $O(N\log N)$ time.

The “Divide and Conquer” Strategy

The famous Cooley-Tukey FFT algorithm is based on a “divide and conquer” insight. Assuming the signal length $N$ is a power of two ($N=2m$), the DFT sum can be split into two parts: one over the even-indexed samples and one over the odd-indexed samples.

The key result of this split is: A DFT of size N can be computed from two DFTs of size N/2.

This suggests a recursive algorithm: to compute an N-point DFT, we first compute the DFTs of its even and odd halves, and then combine them. This process continues until we are left with 1-point DFTs. The total cost of this recursive process is $O(N\log N)$.

As the plot clearly shows, the performance difference is dramatic. The numpy FFT, based on a highly optimized library, is orders of magnitude faster than the naive $O(N^2)$ approaches, making real-time signal processing possible.

The DFT in the Wild: A Tour of Applications

The combination of the Convolution Theorem and the FFT algorithm has unlocked countless technologies.

High-Resolution Evaluation (“Zero-Padding”)

A common task is to plot a smooth curve of the trigonometric polynomial that interpolates our data points. The FFT provides a clever and extremely fast method.

The Recipe for Fast Plotting

1. Get Coefficients: Compute the DFT of your $N$ data points: $\mathbf{c}=\text{fft}(\mathbf{y})$.
2. Pad with Zeros: Create a much larger vector (e.g., of size $M\gg N$) and place the coefficients in it, padding the middle with zeros. This effectively adds zero-amplitude high-frequency components, without changing the original polynomial.
3. Inverse Transform: Perform an M-point inverse FFT on this padded vector. The result will be the values of the original trigonometric interpolant evaluated at $M$ equidistant points, ready for plotting.

Application: Pulse Detection (Smartwatches)

How does a smartwatch measure your heart rate?

1. Signal Acquisition: It uses an optical sensor to get a noisy signal related to blood flow in your wrist.
2. Frequency Analysis: It computes the FFT of this signal and looks at the power spectrum ($|c_k{|}^2$).
3. Find the Peak: The heartbeat is a strong, periodic component that appears as a dominant peak in the power spectrum (ignoring the DC component at $k=0$).
4. Convert to BPM: The index $k$ of this peak corresponds to the dominant frequency. The watch converts this physical frequency (e.g., 1.4 Hz) into beats per minute (1.4 * 60 ≈ 84 BPM).

Application: Magnetic Resonance Imaging (MRI)

MRI is fundamentally a Fourier transform technology. The raw signal the machine measures does not represent the image directly. Instead, it measures the Fourier coefficients of the image in what is called k-space. To get the final image, the computer performs a 2D inverse FFT on the collected k-space data. The peaks in the measured spectrum correspond to the resonant frequencies of different molecules, allowing doctors to distinguish between different types of tissue, like fat and water.

Application: Audio Compression (MP3, AAC)

How can a large audio file be compressed with little perceived loss of quality?

1. Transform: The audio signal is converted to the frequency domain using a transform similar to the FFT.
2. Filter & Quantize: This is the compression step. Based on psychoacoustic models of how the human ear works, coefficients are either discarded or stored with low precision.
   • Low-Pass Filtering: Setting all coefficients above a certain frequency (e.g., 18 kHz) to zero.
   • Thresholding: Keeping only a certain percentage (e.g., 7%) of the coefficients with the largest magnitudes.
3. Store & Reconstruct: The remaining, non-zero coefficients are stored efficiently. During playback, the decoder performs an inverse transform to reconstruct the audio signal.

The "Hello" Demo

As demonstrated in the lecture, even after discarding 97% of the Fourier coefficients and keeping only the 3% with the largest magnitudes, the reconstructed audio signal is still clearly recognizable as the word “Hello.” This showcases the incredible power of frequency-domain sparsity for compression.

The Problem of Aliasing

The DFT relies on sampling a continuous signal. The Nyquist-Shannon sampling theorem states that to perfectly reconstruct a signal, you must sample at a rate at least twice its highest frequency. If you sample too slowly, aliasing occurs.

The Wagon-Wheel Effect

A classic example of aliasing is the wagon-wheel effect in old movies. The wheels of a fast-moving car can appear to spin slowly backward because the camera’s frame rate (the sampling rate) is too low to capture the rapid rotation correctly. The high frequency of the spinning spokes is “aliased” into a low, negative frequency. This is precisely what is shown in the plots.

Continue here: 07 Piecewise Polynomial Interpolation and Splines