Machine Learning · Lecture 18

Lecture 18
Signal Processing and Spectral Analysis

Part V · Signals, senses, structure  |  sinusoids and roots of unity, the discrete Fourier transform and the FFT, sampling and aliasing, convolution and filtering, periodograms and windows, spectrograms and the uncertainty principle, wavelets, matched filtering and the first gravitational wave  |  reading: Oppenheim & Schafer, Discrete-Time Signal Processing (3rd ed., 2010); Cooley & Tukey (1965); Abbott et al. (2016); Shor (1997)

Cartoon: the chord and its notesOne stick figure holds up a scribbly wave and says it looks like noise. The other holds a prism through which the scribble passes and splits into three clean waves of different lengths, and says it is three notes. That's just noise.(it wiggles everywhere) It's three notes.(look at it in frequency)
A signal that is complicated in time can be simple in frequency, and the Fourier transform is the prism
In this lecture
  1. Sinusoids and roots of unity
  2. The discrete Fourier transform and the FFT
  3. Sampling and aliasing
  4. Convolution and filtering
  5. Spectral estimation: periodograms, Welch and windows
  6. Time and frequency together: spectrograms and uncertainty
  7. Wavelets
  8. Matched filtering and the first gravitational wave
  9. Summary, exercises, projects, reading

Part V turns to signals: sound, heartbeats, seismograms, images, the strain of space itself. Any reasonable signal is a sum of sinusoids, and in the frequency view many hard problems become easy: convolution becomes multiplication, a periodic pattern becomes a spike, and broadband noise separates from a signal that lives in a few frequencies. We build this view from the DFT and the FFT and apply it to four real signals: carbon dioxide over Hawaii, sunspots since 1749, a human heartbeat, and the first gravitational wave ever detected. Convolutional networks (Lecture 11) and the image and sound models of Lecture 19 rest on this foundation.

Goals: compute, invert and analyse the DFT and FFT; predict aliases; prove the convolution theorem and design simple filters; estimate spectra with Welch averaging and windows; read a spectrogram and state the uncertainty principle; describe wavelets; and derive the matched filter.

1 — Sinusoids and roots of unity

A sinusoid is a wave \(A\cos(2\pi ft+\varphi)\) that repeats for ever. Its amplitude \(A\) is the peak height; its frequency \(f\) is the number of cycles per second, in hertz (Hz), with period \(1/f\); its phase \(\varphi\) is a time shift measured as an angle, so \(\pi/2\) is a head start of a quarter cycle. The angular frequency \(\omega=2\pi f\) measures the same speed in radians per second.

Why sinusoids? A sinusoid fed into a linear, time-invariant system (Section 4) comes out as a sinusoid of the same frequency, only rescaled and delayed. So such a system is described by two numbers per frequency: a gain and a delay.

Picture an arrow of length \(A\) spinning anticlockwise \(f\) times per second from angle \(\varphi\); its horizontal shadow is the sinusoid. Euler's formula \(e^{i\theta}=\cos\theta+i\sin\theta\) writes the arrow as a complex number, so

$$A\cos(2\pi ft+\varphi)=\operatorname{Re}\big(Ae^{i\varphi}\,e^{2\pi ift}\big).$$

The phasor \(Ae^{i\varphi}\) stores amplitude as length and phase as angle. Delay becomes rotation (multiplication by \(e^{i\alpha}\)), and adding waves of one frequency becomes adding arrows: \(3\cos t\) is an arrow of length 3 at angle 0 and \(4\sin t=4\cos(t-\pi/2)\) one of length 4 at angle \(-\pi/2\); their sum has length 5 and angle \(-0.927\):

$$3\cos t+4\sin t=5\cos(t-0.927).$$

A clockwise arrow \(e^{-2\pi ift}\) has negative frequency. A real cosine is two half-length arrows spinning in opposite directions,

$$\cos\theta=\tfrac12\big(e^{i\theta}+e^{-i\theta}\big),$$

whose imaginary parts cancel. Hence the spectrum of a real signal comes in mirror pairs at \(\pm f\), and the negative half carries no extra information.

For a record of \(n\) samples, the natural test frequencies complete a whole number of cycles in the record. At the sample instants their arrows are powers of \(\omega=e^{-2\pi i/n}\), which turns by \(1/n\) of a revolution per sample. The powers \(\omega^0,\dots,\omega^{n-1}\) are the \(n\)-th roots of unity (solutions of \(z^n=1\)), equally spaced on the unit circle. They cancel: for any integer \(m\) not divisible by \(n\),

$$\sum_{j=0}^{n-1}\omega^{jm}=\frac{1-\omega^{nm}}{1-\omega^m}=0,$$

because \(\omega^{nm}=1\). (Rotating the points by one step leaves the set unchanged, so \(\omega^mS=S\) with \(\omega^m\ne1\), forcing \(S=0\).)

Fourier builder

Build a signal from up to four cosines (frequency, amplitude, phase), sampled 256 times at 128 Hz, and see it in time (top) and frequency (bottom). A frequency that is a whole multiple of 0.5 Hz gives exactly one spike; one such as 10.25 Hz leaks into neighbouring bins. Tick square wave to add odd harmonics of a 2 Hz square wave and watch the corners sharpen.

2 — The discrete Fourier transform and the FFT

definition 18.1 — discrete Fourier transform

The DFT of \(x_0,\dots,x_{n-1}\) is the sequence

$$X_k=\sum_{j=0}^{n-1}x_j\,e^{-2\pi ijk/n},\qquad k=0,\dots,n-1.$$

In matrix form,

$$X=Fx,\qquad F_{kj}=\omega^{kj},\qquad \omega=e^{-2\pi i/n}.$$

Three views of the formula are worth keeping.

Bins are \(f_s/n=1/T\) apart, where \(T\) is the duration, so frequency resolution is set by how long you record, not how fast: waves at \(f\) and \(f+\delta\) drift apart by a cycle only after \(1/\delta\) seconds. Faster sampling extends the visible range (up to \(f_s/2\), Section 3) without sharpening it; appending zeros only interpolates between the same bins.

theorem 18.1 — DFT inversion

The DFT matrix satisfies \(F^{\mathsf H}F=nI\). Consequently the DFT is invertible, with

$$x_j=\frac1n\sum_{k=0}^{n-1}X_k\,e^{2\pi ijk/n},$$

and it preserves energy up to a factor \(n\) (Parseval):

$$\sum_j|x_j|^2=\frac1n\sum_k|X_k|^2.$$

The \((j,l)\) entry of \(F^{\mathsf H}F\) is

$$\sum_k\overline{\omega^{kj}}\,\omega^{kl}=\sum_k\omega^{k(l-j)}.$$

If \(l=j\), every term is 1 and the sum is \(n\).

If \(l\ne j\), then \(0<|l-j|<n\), so \(l-j\) is not divisible by \(n\), and the sum of roots of unity in Section 1 is 0.

Hence \(F^{\mathsf H}F=nI\) and \(F^{-1}=F^{\mathsf H}/n\), which is the inversion formula. Parseval follows:

$$\lVert X\rVert^2=x^{\mathsf H}F^{\mathsf H}Fx=n\lVert x\rVert^2.\qquad\square$$

As a matrix–vector product the DFT costs \(n^2\) multiplications. The fast Fourier transform needs \(O(n\log n)\), by splitting into even- and odd-indexed samples.

theorem 18.2 — the Cooley–Tukey FFT runs in \(O(n\log n)\)

Let \(n\) be a power of 2, and let \(E_k\), \(O_k\) be the length-\(n/2\) DFTs of the even- and odd-indexed samples. For \(k=0,\dots,n/2-1\),

$$X_k=E_k+\omega^kO_k,\qquad X_{k+n/2}=E_k-\omega^kO_k.$$

Computing the DFT recursively in this way takes \(O(n\log n)\) operations.

Split the sum:

$$X_k=\sum_{m}x_{2m}\omega^{2mk}+\omega^k\sum_mx_{2m+1}\omega^{2mk}.$$

Since \(\omega^2=e^{-2\pi i/(n/2)}\) is the root of unity for length \(n/2\), the two sums are \(E_k\) and \(O_k\), which have period \(n/2\) in \(k\).

Replacing \(k\) by \(k+n/2\) multiplies \(\omega^k\) by \(\omega^{n/2}=-1\), giving the second formula.

Combining costs \(O(n)\) per level (\(n/2\) multiplications by \(\omega^k\) and \(n\) additions), so

$$T(n)=2T(n/2)+cn,\qquad T(1)=c.$$

There are \(\log_2n\) levels each costing \(cn\), so

$$T(n)=cn(\log_2n+1)=O(n\log n).\qquad\square$$

Each combining step takes a pair \((E_k,O_k)\), rotates \(O_k\) by the twiddle factor \(\omega^k\), and forms a sum and a difference; drawn as a diagram, this two-in, two-out step is a butterfly. There are \(\log_2n\) layers of \(n/2\) butterflies. For \(n=2^{20}\) the matrix method needs about \(10^{12}\) multiplications and the FFT about \(10^7\): minutes against milliseconds. Gilbert Strang has called the FFT the most important numerical algorithm of our lifetime.

code — the DFT matrix, a recursive FFT, and reading amplitude and phase
# The DFT as a matrix, its inverse, and a hand-written radix-2 FFT
import numpy as np, time
def dft_matrix(n): k = np.arange(n); return np.exp(-2j * np.pi * np.outer(k, k) / n)
F8 = dft_matrix(8)
print(f"F^H F / n = I for n = 8: max deviation {np.abs(F8.conj().T @ F8 / 8 - np.eye(8)).max():.1e}  (Theorem 18.1)")
def fft(x):                                                 # Cooley-Tukey, radix 2, by recursion (Theorem 18.2)
    n = len(x)
    if n == 1: return x.astype(complex)
    E, O = fft(x[0::2]), fft(x[1::2])
    w = np.exp(-2j * np.pi * np.arange(n // 2) / n) * O
    return np.concatenate([E + w, E - w])
rng = np.random.default_rng(0); x = rng.normal(size=1024)
print(f"hand-written FFT vs numpy.fft.fft, n = 1024: max difference {np.abs(fft(x) - np.fft.fft(x)).max():.1e}")
print("    n     matrix DFT (s)   recursive FFT (s)   numpy FFT (s)")
for p in [8, 10, 12]:
    n = 2**p; x = rng.normal(size=n); M = dft_matrix(n)
    t0 = time.perf_counter(); M @ x; t1 = time.perf_counter(); fft(x); t2 = time.perf_counter()
    for _ in range(100): np.fft.fft(x)
    t3 = time.perf_counter()
    print(f"{n:6d}    {t1 - t0:12.5f}     {t2 - t1:12.5f}     {(t3 - t2) / 100:12.6f}")
fs = 100; t = np.arange(0, 2, 1 / fs)                       # 2 s at 100 Hz: bins are 0.5 Hz apart
sig = 1.0 * np.sin(2 * np.pi * 5 * t) + 0.5 * np.cos(2 * np.pi * 12 * t + 0.7)
X = np.fft.rfft(sig); f = np.fft.rfftfreq(len(sig), 1 / fs)
for k in np.argsort(-np.abs(X))[:2]:
    print(f"peak at {f[k]:4.1f} Hz: amplitude {2 * np.abs(X[k]) / len(sig):.3f}, phase {np.angle(X[k]):+.3f} rad")
F^H F / n = I for n = 8: max deviation 7.3e-16  (Theorem 18.1)
hand-written FFT vs numpy.fft.fft, n = 1024: max difference 4.8e-14
    n     matrix DFT (s)   recursive FFT (s)   numpy FFT (s)
   256         0.00021          0.00195         0.000010
  1024         0.00138          0.00835         0.000019
  4096         0.02338          0.03422         0.000072
peak at  5.0 Hz: amplitude 1.000, phase -1.571 rad
peak at 12.0 Hz: amplitude 0.500, phase +0.700 rad

\(F^{\mathsf H}F=nI\) holds to rounding error, and the recursive FFT matches NumPy's to \(5\times10^{-14}\). From 1,024 to 4,096 points the matrix method's time grows by 17 (quadratic law: 16) and the recursive FFT's by about 4 (\(n\log n\): 4.8); interpreter overhead still keeps the pure-Python FFT slower than the matrix product here, while NumPy's compiled FFT is several hundred times faster than either. The spectrum recovers the known ingredients: a 5 Hz sine of amplitude 1 (phase \(-\pi/2\), a sine being a shifted cosine) and a 12 Hz cosine of amplitude 0.5 with phase 0.700.

spot check 18.1

A signal is recorded for 2 seconds at 100 samples per second. How far apart, in hertz, are the DFT's frequency bins?

Bins are \(f_s/n\) apart, and \(n=f_s\times\text{duration}\).
\(n=200\), so the spacing is \(100/200=0.5\) Hz, the reciprocal of the duration. Finer resolution needs a longer record, not faster sampling.
history — heat, asteroids and nuclear tests

Joseph Fourier claimed in an 1807 memoir to the French Academy that any function is a sum of sines and cosines; Lagrange doubted it. The work appeared as Théorie analytique de la chaleur (1822), and making the claim precise took a century. Carl Friedrich Gauss found the divide-and-conquer trick in 1805, interpolating the orbits of the asteroids Pallas and Juno, but his note appeared only posthumously, in Latin, in 1866, and was noticed in 1984 (Heideman, Johnson and Burrus). The modern FFT came from the Cold War: at a 1963 meeting of President Kennedy's Science Advisory Committee, John Tukey sketched it while discussing how to detect Soviet nuclear tests from seismometer records. Richard Garwin put him in touch with James Cooley at IBM, and their 1965 paper in Mathematics of Computation is among the most influential in numerical computing.

3 — Sampling and aliasing

A digital signal is a sequence of samples of a continuous one. Frequencies too high for the sampling rate do not vanish: they reappear disguised as lower ones.

theorem 18.4 — Nyquist–Shannon sampling theorem

Let \(x(t)\) contain no frequencies at or above \(B\) hertz.

$$x(t)=\sum_{j=-\infty}^{\infty}x(j/f_s)\,\operatorname{sinc}\big(f_st-j\big),\qquad\operatorname{sinc}(u)=\frac{\sin\pi u}{\pi u}.$$

(Statement with proof sketch.)

Aliasing. At the sample times \(t_j=j/f_s\),

$$e^{2\pi i(f+mf_s)t_j}=e^{2\pi ift_j}e^{2\pi imj}=e^{2\pi ift_j},$$

so frequencies differing by a multiple of \(f_s\) give identical samples; for real signals \(f\) and \(-f\) also pair up.

Reconstruction. Sampling multiplies \(x(t)\) by a train of impulses spaced \(1/f_s\) apart, whose Fourier transform is an impulse train spaced \(f_s\) apart. By the convolution theorem (Section 4), the spectrum of the samples is that of \(x\) repeated every \(f_s\).

If the spectrum lies in \((-B,B)\) with \(2B<f_s\), the copies do not overlap, and an ideal low-pass filter keeping \((-f_s/2,f_s/2)\) recovers it exactly. That filter's impulse response is the sinc function, which gives the interpolation formula. \(\square\)

The Nyquist frequency \(f_s/2\) belongs to the sampler: the highest frequency it can represent. The Nyquist rate \(2B\) belongs to the signal: the slowest rate that captures it. Frequencies above \(f_s/2\) fold back into \([0,f_s/2]\), like a strip of paper creased at \(f_s/2\) (and at \(f_s\), \(3f_s/2\), …). Sampled at 1,000 Hz, a 900 Hz tone lands at 100 Hz, since for every integer \(j\)

$$\cos\!\left(2\pi\cdot\tfrac{900j}{1000}\right)=\cos\!\left(2\pi j-2\pi\cdot\tfrac{100j}{1000}\right)=\cos\!\left(2\pi\cdot\tfrac{100j}{1000}\right).$$

So aliasing cannot be undone: the two tones give identical numbers. The strict inequality matters too: a sine sampled at exactly twice its frequency can be caught at its zero crossings and vanish, so practical systems leave a margin (CD audio samples at 44,100 Hz to capture sounds up to about 20,000 Hz). In the reconstruction formula each sample owns a sinc bump, equal to 1 at its own instant and 0 at every other.

The theorem is associated with Harry Nyquist (1928) and Claude Shannon (1949), and was found independently by Edmund Whittaker (1915) and Vladimir Kotelnikov (1933). Its practical lesson: remove frequencies above \(f_s/2\) before sampling or downsampling, with an anti-aliasing filter.

code — aliasing, and why to filter before downsampling
# Sampling and aliasing: a 9 Hz sine sampled at 10 Hz looks like 1 Hz
from scipy import signal
f0 = 9.0; dense = np.arange(0, 4, 1 / 1000); low = np.arange(0, 4, 1 / 10)
for fs_ in [100, 20, 10, 12]:
    tt = np.arange(0, 4, 1 / fs_); s = np.sin(2 * np.pi * f0 * tt)
    S = np.abs(np.fft.rfft(s)); ff = np.fft.rfftfreq(len(s), 1 / fs_)
    print(f"sampled at {fs_:3d} Hz (Nyquist {fs_ / 2:4.1f} Hz): apparent frequency {ff[np.argmax(S)]:.2f} Hz")
# an anti-aliasing filter before downsampling removes what cannot be represented
tt = np.arange(0, 4, 1 / 1000); s = np.sin(2 * np.pi * 3 * tt) + np.sin(2 * np.pi * 9 * tt)   # 3 Hz wanted, 9 Hz unwanted
naive = s[::100]                                             # keep every 100th sample: 10 Hz
filt = signal.decimate(signal.decimate(s, 10, ftype='fir'), 10, ftype='fir')   # low-pass, then downsample, twice
for nm, v in [('naive downsampling', naive), ('filter, then downsample', filt)]:
    S = np.abs(np.fft.rfft(v)) / len(v) * 2; ff = np.fft.rfftfreq(len(v), 1 / 10)
    print(f"{nm:24s}: amplitude at 1 Hz {S[np.argmin(abs(ff - 1))]:.3f} (an alias of 9 Hz), at 3 Hz {S[np.argmin(abs(ff - 3))]:.3f}")
sampled at 100 Hz (Nyquist 50.0 Hz): apparent frequency 9.00 Hz
sampled at  20 Hz (Nyquist 10.0 Hz): apparent frequency 9.00 Hz
sampled at  10 Hz (Nyquist  5.0 Hz): apparent frequency 1.00 Hz
sampled at  12 Hz (Nyquist  6.0 Hz): apparent frequency 3.00 Hz
naive downsampling      : amplitude at 1 Hz 1.000 (an alias of 9 Hz), at 3 Hz 1.000
filter, then downsample : amplitude at 1 Hz 0.021 (an alias of 9 Hz), at 3 Hz 0.997

A 9 Hz sine sampled at 100 or 20 Hz is seen at 9 Hz; at 10 Hz (Nyquist 5 Hz) it appears at 1 Hz, and at 12 Hz at 3 Hz, as \(|9-mf_s|\) predicts. Downsampling a 3 Hz plus 9 Hz signal from 1,000 to 10 samples per second by keeping every hundredth sample folds the 9 Hz component onto 1 Hz at full strength (amplitude 1.000), a component never in the original. Low-pass filtering first reduces it to 0.021 and keeps the real 3 Hz one (0.997).

Wagon wheels and aliases

Left: a wheel spoke at the true frequency, drawn at six successive sampling instants (faded to bright). Right: the true signal (grey), its samples (dots) and the lowest-frequency sine through them (dashed). Raise the true frequency past half the sampling rate and the wheel appears to slow, stop and turn backwards, as wagon wheels and helicopter rotors do on film.

(The effect needs a camera or strobe, which really do sample; it is not good evidence that human vision samples in discrete frames.)

spot check 18.2

A 70 Hz tone is sampled at 100 Hz without an anti-aliasing filter. At what frequency (in Hz) does it appear?

Find the integer \(m\) that brings \(|70-100m|\) into \([0,50]\).
\(|70-100|=30\) Hz. At 100 Hz the samples of 70 Hz and 30 Hz cosines are identical, so no later processing can tell them apart.

4 — Convolution and filtering

Smoothing, echo, blurring and the response of an electrode are linear (the response to a sum is the sum of responses) and time-invariant (delaying the input delays the output). Such an LTI system is captured by its impulse response, its output for a single spike. Any input is a sum of scaled, shifted spikes, so the output is a sum of scaled, shifted impulse responses: a convolution, the operation convolutional networks learn (Lecture 11).

definition 18.2 — circular convolution and linear filters

The circular convolution of two length-\(n\) sequences is

$$(a*b)_k=\sum_{j=0}^{n-1}a_j\,b_{(k-j)\bmod n}.$$

A linear time-invariant filter maps an input \(x\) to \(y=h*x\).

A low-pass filter keeps frequencies below a cutoff, a high-pass filter those above, and a band-pass filter those in a range.

theorem 18.3 — the convolution theorem

The DFT of a circular convolution is the product of the DFTs:

$$\widehat{(a*b)}_k=A_kB_k.$$

By definition,

$$\widehat{(a*b)}_k=\sum_l\sum_ja_j\,b_{(l-j)\bmod n}\,\omega^{kl}.$$

Substitute \(m=(l-j)\bmod n\). As \(l\) runs over all residues so does \(m\), and \(\omega^{kl}=\omega^{kj}\omega^{km}\) because \(\omega^{kn}=1\). The double sum factors:

$$\Big(\sum_ja_j\omega^{kj}\Big)\Big(\sum_mb_m\omega^{km}\Big)=A_kB_k.\qquad\square$$

Why it holds: feed \(e^{2\pi ift}\) into an LTI system and out comes \(H(f)e^{2\pi ift}\). Sinusoids are the eigenvectors of every LTI system, with eigenvalue \(H(f)\); in matrix terms, a circular convolution is a circulant matrix, and the DFT diagonalises every circulant matrix. Two practical consequences follow. Filtering is multiplication in frequency, so a filter is designed as a function of frequency. And long convolutions are fast: two FFTs, a product and an inverse FFT cost \(O(n\log n)\) instead of \(O(n^2)\) (zero-padding turns circular into ordinary convolution). A Butterworth filter, used below, is a classic design that is as flat as possible in its pass band, with no ripples, at the cost of a gentler roll-off.

Input view: each sample launches a copy of the impulse response. With input \((1,2,0,0)\) and \(h=(1,0.5)\), the first sample launches \((1,0.5)\), the second launches \((2,1)\) one step later, and the output is \((1,2.5,1,0)\); \(h=(1,0,\dots,0,0.5)\) is an echo at half strength. Output view: each output is a weighted sum of inputs under the flipped impulse response. Positive weights summing to 1 give a moving average, which blurs; weights of both signs compute differences, which sharpen. (Convolutional layers in neural networks skip the flip and compute a cross-correlation; since the weights are learned, nothing depends on it.)

Our first real signal is a heartbeat. An electrocardiogram (ECG) records the heart's electrical activity at the skin. Each beat shows a small P wave (the impulse that makes the upper chambers contract), a sharp QRS complex whose tall spike is the R wave (the main chambers contracting), and a broader T wave (their electrical recovery). The interval between R waves gives the heart rate.

data — MIT-BIH Arrhythmia Database, record 100

A 30-minute two-lead ambulatory ECG, sampled at 360 Hz with every beat annotated by two cardiologists, from the MIT-BIH Arrhythmia Database (Moody and Mark, 2001), recorded at Boston's Beth Israel Hospital in 1975–1979 and distributed by PhysioNet (Goldberger et al., 2000). Record 100 (lead MLII) ships as sample data with the wfdb Python package (repository MIT-LCP/wfdb-python on GitHub); PhysioNet itself was not reachable from the build environment.

code — the convolution theorem, heart rate from the spectrum, and removing baseline wander
# The convolution theorem, and filtering an electrocardiogram
import wfdb
a = rng.normal(size=256); b = rng.normal(size=256)
direct = np.array([sum(a[j] * b[(k - j) % 256] for j in range(256)) for k in range(256)])
via_fft = np.real(np.fft.ifft(np.fft.fft(a) * np.fft.fft(b)))
print(f"circular convolution: direct sum vs inverse FFT of the product, max difference {np.abs(direct - via_fft).max():.1e}  (Theorem 18.3)")
rec = wfdb.rdrecord('data/100'); ann = wfdb.rdann('data/100', 'atr'); fsE = rec.fs
ecg = rec.p_signal[:, 0]                                    # lead MLII, millivolts, 360 Hz, 30 minutes
beats = ann.sample[np.isin(ann.symbol, ['N', 'A', 'V'])]
print(f"MIT-BIH record 100: {len(ecg) / fsE / 60:.1f} min at {fsE} Hz; {len(beats)} annotated beats -> mean heart rate "
      f"{60 * (len(beats) - 1) / ((beats[-1] - beats[0]) / fsE):.1f} beats/min")
seg = ecg[:60 * fsE]                                         # the first minute
fW, P = signal.welch(seg - seg.mean(), fsE, nperseg=8 * fsE)
band = (fW > 0.7) & (fW < 3); print(f"strongest spectral line between 0.7 and 3 Hz: {fW[band][np.argmax(P[band])]:.3f} Hz "
      f"= {60 * fW[band][np.argmax(P[band])]:.1f} beats/min; beats annotated in that minute: {np.sum(beats < 60 * fsE)}")
drift = 0.3 * np.sin(2 * np.pi * 0.15 * np.arange(len(seg)) / fsE)   # add slow breathing-like baseline wander
noisy = seg + drift
bh, ah = signal.butter(2, 0.5, 'highpass', fs=fsE); hp = signal.filtfilt(bh, ah, noisy)
bl, al = signal.butter(4, 40, 'lowpass', fs=fsE)
print(f"added baseline wander (0.15 Hz, 0.3 mV): rms deviation from the original {np.sqrt(np.mean((noisy - seg) ** 2)):.3f} mV; "
      f"after a 0.5 Hz high-pass: rms deviation from the high-passed original {np.sqrt(np.mean((hp - signal.filtfilt(bh, ah, seg)) ** 2)):.4f} mV")
circular convolution: direct sum vs inverse FFT of the product, max difference 5.7e-14  (Theorem 18.3)
MIT-BIH record 100: 30.1 min at 360 Hz; 2273 annotated beats -> mean heart rate 75.5 beats/min
strongest spectral line between 0.7 and 3 Hz: 1.250 Hz = 75.0 beats/min; beats annotated in that minute: 74
added baseline wander (0.15 Hz, 0.3 mV): rms deviation from the original 0.212 mV; after a 0.5 Hz high-pass: rms deviation from the high-passed original 0.0022 mV

Direct circular convolution and the FFT route agree to \(6\times10^{-14}\). The 2,273 annotated beats over 30 minutes give a mean of 75.5 beats per minute. In the first minute, the strongest Welch line between 0.7 and 3 Hz is at 1.250 Hz, or 75.0 beats per minute, against 74 annotated beats: a heart rate read from the spectrum without detecting a single beat. A slow 0.15 Hz wander of 0.3 mV moves the trace by 0.212 mV on average; a second-order Butterworth high-pass at 0.5 Hz, applied forwards and backwards, removes it to within 0.002 mV.

Baseline wander (drift from breathing, movement and electrode contact) lives below about 0.5 Hz and is removed by a high-pass filter; mains hum, at 60 Hz in North America (50 Hz in Europe), by a narrow notch. A one-pass filter delays frequencies unequally and bends the waves; running it forwards then backwards cancels the delays. This zero-phase filtering needs the whole record, so it suits offline analysis. The American Heart Association's 2007 recommendations ask for a low-frequency cutoff of 0.05 Hz to avoid distorting the ST segment (between the QRS complex and the T wave, which signals heart attacks), relaxed to as much as 0.67 Hz for linear digital filters with zero phase distortion (Kligfield et al., 2007).

Filter designer on an ECG

About 11 seconds of record 100 (grey) and the filtered output (rose), with both spectra below on a log frequency axis. Add baseline wander or 60 Hz hum, then remove them with the high-pass and low-pass cutoffs (smooth fourth-order responses applied in frequency). Push the high-pass above 5 Hz or the low-pass below 15 Hz and the heartbeat itself distorts: the waves cardiologists read live in the band you are removing.

5 — Spectral estimation: periodograms, Welch and windows

Most real signals (weather, sunspots, detector noise) are better treated as random. For a stationary signal, whose mean, variance and correlations do not change over time, the power spectral density \(S(f)\) (PSD) shows how the variance is spread over frequency; its total area is the variance. A flat PSD is white noise. The obvious estimate squares the DFT.

definition 18.3 — periodogram and Welch's method

The periodogram of \(x_0,\dots,x_{n-1}\), sampled at rate \(f_s\), is

$$\hat S(f_k)=\frac1{nf_s}|X_k|^2.$$

It is usually computed after multiplying the data by a window \(w_j\) that tapers to zero at the ends, normalising by \(\sum_jw_j^2\) instead of \(n\).

Welch's method (1967) cuts the series into \(K\) overlapping segments of length \(L\), computes a windowed periodogram of each, and averages them.

theorem 18.5 — the periodogram is asymptotically unbiased but not consistent; averaging helps

Let the series be stationary with continuous spectral density, and fix \(0<f<f_s/2\). As \(n\to\infty\),

$$\mathbb E\hat S(f)\to S(f),\qquad\operatorname{Var}\hat S(f)\to S(f)^2.$$

(Proof sketch.)

Take Gaussian white noise with variance \(\sigma^2\). For \(0<k<n/2\), the real and imaginary parts of \(X_k\) are linear combinations of the samples with orthogonal coefficient vectors (Theorem 18.1), so they are independent normals with variance \(n\sigma^2/2\) each.

Then \(|X_k|^2/(n\sigma^2/2)\) is a sum of two squared standard normals, \(\chi^2_2\), with mean 2 and variance 4. So \(\hat S\propto|X_k|^2\) has standard deviation equal to its mean, for every \(n\): more data give more frequencies, not better estimates at each one.

For a general stationary series, the DFT coefficients are asymptotically independent complex normals with variance proportional to \(S(f_k)\), with the same conclusion.

Averaging \(K\) independent \(\chi^2_2\) variables gives \(\chi^2_{2K}/K\), with relative standard deviation \(1/\sqrt K\). \(\square\)

A longer record gives more bins, but each is still estimated from two numbers (the real and imaginary parts of one coefficient). So a white-noise periodogram never looks flat, and a single tall spike is weak evidence of a real cycle.

Welch's method averages \(K\) noisy snapshots, cutting the noise by \(\sqrt K\), as bagging does in Lecture 8; but each segment is \(K\) times shorter, so its bins are \(K\) times wider. This is the bias–variance trade-off of kernel density estimation (Lecture 14).

Leakage comes from a hidden assumption: the DFT treats the record as one period of a repeating signal. A sinusoid that does not complete a whole number of cycles leaves a jump at the seam, and building a jump takes many frequencies, so power leaks into distant bins. A window (or taper) fades the record smoothly to zero at both ends, removing the jump. The Hann window,

$$w_j=\sin^2\big(\pi j/(n-1)\big),$$

is a single raised-cosine bump (after the meteorologist Julius von Hann; the "Hamming" window is a different one). The price is some discarded data and peaks about twice as wide. And the periodogram is only asymptotically unbiased: in a finite record, leakage from a strong peak can swamp weak parts of the spectrum, a bias that windows reduce but do not remove (Percival and Walden, 1993).

Spectra are usually plotted in decibels, \(10\log_{10}\) of a power ratio: 10 dB is a factor of 10 in power, 3 dB roughly a factor of 2, and −30 dB one thousandth.

code — periodogram variance, leakage, and the spectra of sunspots and carbon dioxide
# Spectral estimation: the periodogram does not settle down; Welch averaging does; windows control leakage
import pandas as pd
for n in [256, 4096, 65536]:
    w = rng.normal(size=n); P = np.abs(np.fft.rfft(w))[1:-1] ** 2 / n   # periodogram of unit white noise (true spectrum 1)
    fW_, PW = signal.welch(w, nperseg=256, return_onesided=False)
    print(f"white noise, n = {n:6d}: periodogram mean {P.mean():.3f}, sd {P.std():.3f};   Welch (256-point segments) mean "
          f"{PW.mean():.3f}, sd {PW.std():.3f}")
tt = np.arange(512); s = np.sin(2 * np.pi * 50.5 * tt / 512)            # a sine exactly between two DFT bins
for nm, win in [('rectangular', np.ones(512)), ('Hann', signal.windows.hann(512))]:
    S = np.abs(np.fft.rfft(s * win)) ** 2; S /= S.max()
    print(f"{nm:11s} window: power 20 bins from the peak {10 * np.log10(S[70]):6.1f} dB, 100 bins away {10 * np.log10(S[150]):6.1f} dB")
ss = pd.read_csv('data/sunspot.month.csv'); spots = ss.value.to_numpy()
print(f"sunspots: {len(spots)} monthly values, {ss.time.iloc[0]:.0f} to {ss.time.iloc[-1]:.2f}")
fS, PS = signal.welch(spots - spots.mean(), fs=12, nperseg=1024, window='hann')   # frequency in cycles per year
pk = fS[1:][np.argmax(PS[1:])]; print(f"  Welch spectrum peak at {pk:.4f} cycles/year = period {1 / pk:.2f} years")
fP, PP = signal.periodogram(spots - spots.mean(), fs=12, window='hann'); band = (fP > 0.05) & (fP < 0.2)
pk2 = fP[band][np.argmax(PP[band])]; print(f"  full-length periodogram peak at period {1 / pk2:.2f} years (finer resolution, noisier)")
co = pd.read_csv('data/co2-mm-mlo.csv', header=0, names=['date', 'dec', 'avg', 'deseas', 'ndays', 'sd', 'unc'])
co = co[co.avg > 0]; y = co.avg.to_numpy(); tdec = co.dec.to_numpy()
resid = y - np.polyval(np.polyfit(tdec, y, 3), tdec)                     # remove the long-term rise
fC, PC = signal.periodogram(resid, fs=12, window='hann')
top = fC[np.argsort(-PC)[:3]]
print(f"Mauna Loa CO2: {len(y)} months, {co.date.iloc[0]} to {co.date.iloc[-1]}, from {y[0]:.2f} to {y[-1]:.2f} ppm; "
      f"spectral peaks of the detrended series at {', '.join(f'{v:.3f}' for v in sorted(top))} cycles/year")
amp = np.ptp(pd.Series(resid).groupby(np.arange(len(resid)) % 12).mean())
print(f"  peak-to-trough of the average seasonal cycle: {amp:.2f} ppm")
white noise, n =    256: periodogram mean 1.115, sd 0.964;   Welch (256-point segments) mean 1.004, sd 0.832
white noise, n =   4096: periodogram mean 0.994, sd 1.008;   Welch (256-point segments) mean 0.989, sd 0.159
white noise, n =  65536: periodogram mean 1.001, sd 0.995;   Welch (256-point segments) mean 0.997, sd 0.064
rectangular window: power 20 bins from the peak  -33.1 dB, 100 bins away  -49.7 dB
Hann        window: power 20 bins from the peak  -85.9 dB, 100 bins away -130.4 dB
sunspots: 3310 monthly values, 1749 to 2024.75
  Welch spectrum peak at 0.0938 cycles/year = period 10.67 years
  full-length periodogram peak at period 11.03 years (finer resolution, noisier)
Mauna Loa CO2: 822 months, 1958-03 to 2026-08, from 315.71 to 427.55 ppm; spectral peaks of the detrended series at 0.993, 1.007, 2.000 cycles/year
  peak-to-trough of the average seasonal cycle: 6.29 ppm

For unit white noise the periodogram's mean is close to 1 at every length, but its standard deviation stays at about 1 whether there are 256 or 65,536 samples, as Theorem 18.5 says. Welch's average over 256-point segments has standard deviation 0.832 with one segment, 0.159 with 4,096 samples and 0.064 with 65,536, falling roughly like \(1/\sqrt K\) (the last value is inflated by the near-zero bin at frequency 0, which detrending removes). For a sine midway between two bins, the rectangular window leaves power only 33 dB below the peak 20 bins away; a Hann window pushes it to 86 dB below, at the price of a slightly wider peak.

0-40-80-120050100150200250DFT bin (the sine sits at bin 50.5) · power in dBrectangular windowHann window
Leakage: the power spectrum of a sine at bin 50.5 with a rectangular window (sky) and a Hann window (rose), in decibels relative to the peak.
data — sunspots and Mauna Loa carbon dioxide

Sunspots: the monthly mean total sunspot number (version 2.0) from the Royal Observatory of Belgium's SILSO centre, January 1749 to October 2024 (3,310 months), in the Rdatasets copy of R's sunspot.month. Carbon dioxide: monthly mean CO₂ concentration at Mauna Loa Observatory, Hawaii, begun by Charles David Keeling of the Scripps Institution of Oceanography in 1958 and continued with NOAA, March 1958 to August 2026 (822 months), from the datasets/co2-ppm repository on GitHub, which mirrors NOAA's file; NOAA's server was not reachable.

175018001850190019502000010020030035112040monthly sunspot numberperiod (years, log scale)
Left: monthly sunspot numbers since 1749. Right: their Welch spectrum against period (log scale), with a single dominant peak near 11 years.

The sunspot spectrum peaks at 10.67 years with Welch's method (segments of 1,024 months, resolution about 0.012 cycles per year) and at 11.03 years in the finer, noisier full periodogram, a difference within the Welch resolution. The solar cycle's length varies from about 9 to 14 years, hence the broad peak. Mauna Loa CO₂ rose from 315.71 to 427.55 ppm; after removing a cubic trend, the spectrum peaks at one cycle per year (split between bins at 0.993 and 1.007) and at two cycles per year. The annual cycle, about 6.3 ppm from peak to trough, is the breathing of the northern forests, which take up carbon in summer and release it in winter.

The second peak is a harmonic, a whole-number multiple of the fundamental frequency. A non-sinusoidal periodic shape needs harmonics, as the square wave of Section 1 does; CO₂ falls quickly in the northern growing season and recovers slowly. The sunspot cycle is lopsided too, with a rapid rise and slower decline.

spot check 18.3

A Welch estimate averages 100 roughly independent segment periodograms. By what factor is the relative standard deviation at each frequency reduced, compared with a single periodogram?

Averaging \(K\) independent estimates divides the standard deviation by \(\sqrt K\).
\(1/\sqrt{100}=0.1\), a tenfold reduction, as the white-noise test shows. With the same total length, each segment is 100 times shorter, so the resolution is 100 times coarser.

6 — Time and frequency together: spectrograms and uncertainty

Speech, music, birdsong and gravitational waves change frequency over time, which a single spectrum averages away. The short-time Fourier transform computes spectra of short, overlapping windows and lays them side by side.

definition 18.4 — short-time Fourier transform and spectrogram

With a window \(w\) of length \(L\) and hop \(h\), the STFT is

$$X(m,k)=\sum_{j=0}^{L-1}x_{mh+j}\,w_j\,e^{-2\pi ijk/L}.$$

The spectrogram is \(|X(m,k)|^2\), displayed as an image with time \(m\) across and frequency \(k\) up.

A spectrogram reads like a musical score: time runs right, pitch up, and a note is a stack of bars at its harmonics. A chirp, whose frequency sweeps like a bird's call, draws a sloping curve. The bars cannot be sharp in both directions: a short window locates events in time but has coarse bins (\(f_s/L\)); a long window resolves frequency but smears events. Telling 440 Hz from 441 Hz takes about one second of listening. The trade-off is a theorem.

theorem 18.6 — the Gabor uncertainty principle

Let \(w(t)\) have finite energy. Let \(\sigma_t\) be the standard deviation of the time distribution \(|w(t)|^2/\lVert w\rVert^2\), and \(\sigma_f\) that of the frequency distribution \(|W(f)|^2/\lVert W\rVert^2\). Then

$$\sigma_t\,\sigma_f\;\ge\;\frac1{4\pi},$$

with equality exactly for Gaussian pulses

$$w(t)\propto e^{-(t-t_0)^2/2s^2}e^{2\pi if_0t}$$

(Gabor, 1946). (Statement; the proof is the Cauchy–Schwarz argument behind Heisenberg's uncertainty relation.)

The mathematics is Heisenberg's (position and momentum are a Fourier pair), but here it is a plain fact about functions, not about measurement.

code — spectrograms of a chirp at three window lengths; the uncertainty product of three windows
# Time-frequency: the spectrogram of a chirp, and the uncertainty principle for windows
fsC = 1000; tC = np.arange(0, 2, 1 / fsC); chirp = signal.chirp(tC, f0=20, t1=2, f1=300, method='quadratic')
for nps in [32, 128, 512]:
    fq, tq, Sxx = signal.spectrogram(chirp, fsC, nperseg=nps, noverlap=nps // 2)
    i = np.argmin(abs(tq - 1.0)); est = fq[np.argmax(Sxx[:, i])]
    print(f"window {nps:3d} samples ({1000 * nps / fsC:3.0f} ms): frequency resolution {fsC / nps:5.1f} Hz, "
          f"time step {1000 * (nps // 2) / fsC:3.0f} ms; estimated frequency at t = 1 s {est:6.1f} Hz (true {20 + 280 * 0.25:.0f} Hz)")
def spreads(w, fs_=1000.0):                                  # rms durations in time and frequency of a window (Theorem 18.6)
    n = len(w); t_ = (np.arange(n) - (n - 1) / 2) / fs_; p = w**2 / np.sum(w**2)
    W = np.fft.fftshift(np.fft.fft(w, 64 * n)); fq_ = np.fft.fftshift(np.fft.fftfreq(64 * n, 1 / fs_)); q = np.abs(W) ** 2 / np.sum(np.abs(W) ** 2)
    return np.sqrt(np.sum(p * t_**2)), np.sqrt(np.sum(q * fq_**2))
for nm, w in [('Gaussian', signal.windows.gaussian(1001, 60)), ('Hann', signal.windows.hann(401)), ('rectangular', np.ones(201))]:
    st, sf = spreads(w); print(f"{nm:11s} window: sigma_t sigma_f = {st * sf:.4f}   (lower bound 1/(4 pi) = {1 / (4 * np.pi):.4f})")
window  32 samples ( 32 ms): frequency resolution  31.2 Hz, time step  16 ms; estimated frequency at t = 1 s   93.8 Hz (true 90 Hz)
window 128 samples (128 ms): frequency resolution   7.8 Hz, time step  64 ms; estimated frequency at t = 1 s   93.8 Hz (true 90 Hz)
window 512 samples (512 ms): frequency resolution   2.0 Hz, time step 256 ms; estimated frequency at t = 1 s   74.2 Hz (true 90 Hz)
Gaussian    window: sigma_t sigma_f = 0.0796   (lower bound 1/(4 pi) = 0.0796)
Hann        window: sigma_t sigma_f = 0.0817   (lower bound 1/(4 pi) = 0.0796)
rectangular window: sigma_t sigma_f = 1.0846   (lower bound 1/(4 pi) = 0.0796)

The chirp rises from 20 to 300 Hz over two seconds, reaching 90 Hz at \(t=1\) s. With 32 or 128 ms windows the peak at one second is at 93.8 Hz, within one bin of the truth (bins 31 Hz and 8 Hz wide). A 512 ms window has 2 Hz bins, but the frequency changes by more than 70 Hz within it, and the estimate falls to 74.2 Hz: fine resolution is useless for a signal that does not hold still. The Gaussian window attains the bound \(1/4\pi=0.0796\), the Hann window comes close (0.0817), and the sharp-edged rectangular window is far from it.

Spectrogram of a chirp

A two-second chirp sweeping from 20 to 300 Hz, sampled at 1,000 Hz. Change the window length (Hann, 75% overlap) and watch the curve sharpen in frequency and blur in time, or the reverse. No window makes it sharp in both.

spot check 18.4

Speech is often analysed at 8,000 samples per second with windows of 256 samples. What is the frequency resolution in hertz, and roughly how long is each window?

Resolution is \(f_s/L\); duration is \(L/f_s\).
\(8000/256=31.25\) Hz, with 32 ms windows: short enough that the vocal tract barely changes within one, fine enough to separate vowel formants.

7 — Wavelets

The STFT uses one window length for all frequencies. Wavelets use short windows for high frequencies and long ones for low: a multiscale analysis suited to sharp spikes on slow trends, like an ECG.

A wavelet is a short wiggle with zero average. The wavelet transform compares the signal with shifted copies (different times) and stretched or squeezed copies (different scales), like a mathematical microscope. Its time–frequency cells keep the same area, as the uncertainty principle demands, but change shape with scale.

definition 18.5 — the Haar wavelet transform

One level of the Haar transform maps \(x\) (of even length) to scaled pairwise averages and differences:

$$a_j=\frac{x_{2j}+x_{2j+1}}{\sqrt2},\qquad d_j=\frac{x_{2j}-x_{2j+1}}{\sqrt2}.$$

Haar by hand. Ignoring the \(\sqrt2\), take \((8,6,2,4)\). Pairwise averages give \((7,3)\) and halved differences \((1,-1)\). Repeating on the averages gives 5 and 2. So the signal is "level 5, a coarse step of 2, and fine details 1 and −1", from which it is rebuilt exactly. Where a signal is smooth the differences are tiny, so smooth signals are sparse in this basis: a few large coefficients carry the features.

Noise is not sparse: white noise spreads evenly over all coefficients at a small size \(\sigma\). So zeroing coefficients below a threshold \(\lambda\) removes noise and keeps features (Donoho and Johnstone, 1994). Their universal threshold

$$\lambda=\sigma\sqrt{2\ln n}$$

is roughly the largest value pure noise produces among \(n\) coefficients. Hard thresholding keeps or kills each coefficient; soft thresholding also shrinks every survivor by \(\lambda\), and solves an \(L_1\)-penalised least-squares problem, the lasso of Lecture 3 in a wavelet basis. That shrinkage also lowers the peaks of genuine sharp features, as the code shows. JPEG 2000 compresses images with wavelets, and the FBI has stored fingerprints with wavelet compression since the 1990s.

code — a Haar transform by hand, and wavelet denoising of an ECG
# Wavelets: a Haar transform by hand, and wavelet denoising of an ECG
import pywt
def haar(x):                                                 # one level: scaled averages and differences of pairs
    return (x[0::2] + x[1::2]) / np.sqrt(2), (x[0::2] - x[1::2]) / np.sqrt(2)
v = rng.normal(size=1024); a1, d1 = haar(v)
print(f"Haar transform is orthonormal: energy {np.sum(v**2):.4f} = {np.sum(a1**2) + np.sum(d1**2):.4f}; "
      f"matches PyWavelets: {np.allclose(pywt.dwt(v, 'haar')[1], d1) or np.allclose(pywt.dwt(v, 'haar')[1], -d1)}")
clean = seg[:4096]; noisyE = clean + rng.normal(0, 0.1, len(clean))   # add white noise, sd 0.1 mV
coeffs = pywt.wavedec(noisyE, 'db4', level=6); sigma = np.median(np.abs(coeffs[-1])) / 0.6745
thr = sigma * np.sqrt(2 * np.log(len(noisyE)))                         # Donoho-Johnstone universal threshold
den = pywt.waverec([coeffs[0]] + [pywt.threshold(c, thr, 'soft') for c in coeffs[1:]], 'db4')[:len(clean)]
b40, a40 = signal.butter(4, 40, 'lowpass', fs=fsE); lp = signal.filtfilt(b40, a40, noisyE)
rmse = lambda z: np.sqrt(np.mean((z - clean) ** 2))
print(f"ECG + white noise (sd 0.1 mV): rms error noisy {rmse(noisyE):.4f} mV, 40 Hz low-pass {rmse(lp):.4f} mV, "
      f"wavelet soft threshold {rmse(den):.4f} mV")
pk_true = np.max(clean); print(f"R-wave peak height: clean {pk_true:.3f} mV, low-pass {np.max(lp):.3f}, wavelet {np.max(den):.3f}; "
      f"wavelet coefficients kept {sum(np.sum(np.abs(c) > thr) for c in coeffs[1:])} of {sum(len(c) for c in coeffs[1:])}")
denH = pywt.waverec([coeffs[0]] + [pywt.threshold(c, thr, 'hard') for c in coeffs[1:]], 'db4')[:len(clean)]
print(f"hard threshold instead of soft: rms error {rmse(denH):.4f} mV, R-wave peak {np.max(denH):.3f} mV")
Haar transform is orthonormal: energy 973.2307 = 973.2307; matches PyWavelets: True
ECG + white noise (sd 0.1 mV): rms error noisy 0.0996 mV, 40 Hz low-pass 0.0487 mV, wavelet soft threshold 0.0794 mV
R-wave peak height: clean 0.960 mV, low-pass 0.960, wavelet 0.565; wavelet coefficients kept 102 of 4064
hard threshold instead of soft: rms error 0.0538 mV, R-wave peak 1.050 mV

The hand-written Haar step preserves energy and matches PyWavelets. Denoising is a mixed result. With white noise of standard deviation 0.1 mV, the textbook recipe (Daubechies-4, universal threshold, soft thresholding) reduces the error from 0.0996 to 0.0794 mV, but a plain 40 Hz low-pass does better (0.0487 mV), and soft thresholding cuts the R-wave peaks from 0.960 to 0.565 mV, a distortion a cardiologist would not accept. Hard thresholding preserves the peaks (1.050 mV, slightly overshooting) and nearly matches the low-pass (0.0538 mV). With the heartbeat mostly below 40 Hz and the noise spread evenly above, a frequency cut is hard to beat; wavelets earn their keep when signal and noise overlap in frequency but not in scale.

8 — Matched filtering and the first gravitational wave

We know the shape \(s\) of a signal buried in noise, but not when it arrives. Which linear filter maximises the signal-to-noise ratio (SNR), the signal's contribution to a statistic over the noise's standard deviation? The answer: slide a template of the expected shape along the data and measure the match at each position.

theorem 18.7 — the matched filter maximises the signal-to-noise ratio

Let \(x=s+n\), where \(n\) is noise with zero mean and covariance \(C\) (for stationary noise, diagonal in frequency with entries proportional to the PSD \(S(f)\)). For linear statistics \(y=h^{\mathsf H}x\), define

$$\mathrm{SNR}(h)=\frac{|h^{\mathsf H}s|}{\sqrt{h^{\mathsf H}Ch}}.$$

It is maximised by \(h\propto C^{-1}s\), with maximum

$$\max_h\mathrm{SNR}(h)=\sqrt{s^{\mathsf H}C^{-1}s}.$$

In the frequency domain the statistic is

$$\sum_f\frac{\overline{S_{\text{sig}}(f)}\,X(f)}{S(f)}:$$

correlate data with template, weighting each frequency by the inverse noise power.

Write \(u=C^{1/2}h\). Then

$$h^{\mathsf H}s=u^{\mathsf H}C^{-1/2}s,\qquad h^{\mathsf H}Ch=\lVert u\rVert^2.$$

By Cauchy–Schwarz, \(|u^{\mathsf H}C^{-1/2}s|\le\lVert u\rVert\,\lVert C^{-1/2}s\rVert\), so

$$\mathrm{SNR}(h)\le\lVert C^{-1/2}s\rVert=\sqrt{s^{\mathsf H}C^{-1}s},$$

with equality exactly when \(u\propto C^{-1/2}s\), i.e. \(h\propto C^{-1}s\).

For stationary noise the DFT diagonalises \(C\) (by the convolution theorem), with diagonal proportional to \(S(f)\), which gives the frequency-domain form. \(\square\)

With white noise, a filter \(h\) collects signal \(\langle h,s\rangle\) and noise of standard deviation \(\sigma\lVert h\rVert\); any part of \(h\) pointing away from \(s\) collects only noise. Where noise is louder, evidence counts less, as in weighted least squares. Dividing by the noise spectrum, whitening, equalises the noise, after which plain correlation with the whitened template is optimal. FFTs compute the SNR for every arrival time at once.

data — LIGO strain around GW150914

At 09:50:45 UTC on 14 September 2015 the two Advanced LIGO detectors, at Hanford, Washington, and Livingston, Louisiana, recorded a gravitational wave from the merger of two black holes of about 36 and 29 solar masses, roughly 1.3 billion light-years away (Abbott et al., 2016). We use 32 seconds of the calibrated strain from each detector at 4,096 samples per second, and a matching waveform template, released by the LIGO Open Science Center (now GWOSC) under CC BY 4.0. The files come from the LIGO tutorial repository losc-tutorial/LOSC_Event_tutorial on GitHub, because the GWOSC server was not reachable. The signal changed the detectors' 4-km arms by about \(10^{-21}\) of their length.

A passing gravitational wave alternately stretches and squeezes space in perpendicular directions. LIGO, an L-shaped laser interferometer with 4 km arms, measures the difference in arm lengths as a strain \(h=\Delta L/L\). GW150914's peak strain was \(1.0\times10^{-21}\), so each arm changed by about \(4\times10^{-18}\) m, roughly one four-hundredth of a proton's width; at the same strain the Earth–Sun distance would change by about the width of an atom.

The expected shape is a chirp: orbiting black holes radiate, spiral closer and orbit faster until they merge, and the wave frequency (twice the orbital frequency) and amplitude rise to the merger. GW150914 swept from 35 to 250 Hz in about two tenths of a second; at a wave frequency of 150 Hz the black holes orbited 75 times a second, only a few hundred kilometres apart, too close for anything less compact than black holes (Abbott et al., 2016).

code — whitening, band-passing and matched filtering
# GW150914: whitening, band-passing and matched filtering reveal the first gravitational-wave chirp
import h5py
def load(f):
    with h5py.File(f, 'r') as h: return h['strain/Strain'][()], h['meta/GPSstart'][()]
hH, gps0 = load('data/H-H1_LOSC_4_V2-1126259446-32.hdf5'); hL, _ = load('data/L-L1_LOSC_4_V2-1126259446-32.hdf5')
with h5py.File('data/GW150914_4_template.hdf5', 'r') as h: tmpl = h['template'][()]
fsL = 4096; tL = gps0 + np.arange(len(hH)) / fsL; tev = 1126259462.44
print(f"two detectors, {len(hH) / fsL:.0f} s each at {fsL} Hz; raw strain sd: Hanford {hH.std():.2e}, Livingston {hL.std():.2e}")
def psd(x): f_, P_ = signal.welch(x, fsL, nperseg=4 * fsL); return f_, P_
fP_, PH = psd(hH); _, PL = psd(hL)
print(f"Hanford amplitude spectral density: {np.sqrt(np.interp(30, fP_, PH)):.1e} at 30 Hz, {np.sqrt(np.interp(150, fP_, PH)):.1e} at 150 Hz, "
      f"{np.sqrt(np.interp(1000, fP_, PH)):.1e} at 1000 Hz (per root Hz)")
win = signal.windows.tukey(len(hH), 0.1); freqs = np.fft.rfftfreq(len(hH), 1 / fsL)
def whiten(x, P): X = np.fft.rfft(x * win); return np.fft.irfft(X / np.sqrt(np.interp(freqs, fP_, P) / 2 / (1 / fsL)), n=len(x))
bb, ab = signal.butter(4, [35, 350], btype='band', fs=fsL)
wH = signal.filtfilt(bb, ab, whiten(hH, PH)); wL = signal.filtfilt(bb, ab, whiten(hL, PL))
near = np.abs(tL - tev) < 0.2; quiet = (np.abs(tL - tev) > 2) & (np.abs(tL - tev) < 12)
print(f"whitened, band-passed Hanford: peak |value| within 0.2 s of the event {np.abs(wH[near]).max():.1f}, "
      f"typical (sd) elsewhere {wH[quiet].std():.2f}")
# matched filter (Theorem 18.7): correlate data and template, both weighted by 1/PSD, following the LOSC tutorial
tc = tmpl[0] + 1j * tmpl[1]                                  # plus and cross polarisations as one complex template
dw = signal.windows.tukey(len(tc), 1 / 8); fall = np.fft.fftfreq(len(hH), 1 / fsL); df = abs(fall[1])
Tf = np.fft.fft(tc * dw) / fsL
def snr_series(x, P):
    Df = np.fft.fft(x * dw) / fsL; Pf = np.interp(np.abs(fall), fP_, P)
    z = 2 * np.fft.ifft(Df * Tf.conj() / Pf) * fsL                       # filter output at every time shift
    sigma = np.sqrt(np.abs(np.sum(Tf * Tf.conj() / Pf) * df))           # normalisation: output sd for pure noise
    return np.abs(np.roll(z / sigma, len(z) // 2))
for nm, x, P in [('Hanford', hH, PH), ('Livingston', hL, PL)]:
    rho = snr_series(x, P); keep = (tL > gps0 + 4) & (tL < gps0 + 28)
    i = np.argmax(np.where(keep, rho, 0)); bg = rho[keep & (np.abs(tL - tL[i]) > 1)]
    globals()['rho_' + nm[0]] = rho; globals()['tpk_' + nm[0]] = tL[i]
    print(f"{nm:10s}: matched-filter SNR peaks at {rho[i]:5.1f} at GPS {tL[i]:.4f}; median elsewhere {np.median(bg):.2f}, max elsewhere {bg.max():.2f}")
print(f"arrival-time difference Hanford - Livingston: {1000 * (tpk_H - tpk_L):+.1f} ms (light travel time between the sites: 10 ms)")
two detectors, 32 s each at 4096 Hz; raw strain sd: Hanford 2.20e-19, Livingston 2.34e-19
Hanford amplitude spectral density: 3.7e-23 at 30 Hz, 8.0e-24 at 150 Hz, 2.7e-23 at 1000 Hz (per root Hz)
whitened, band-passed Hanford: peak |value| within 0.2 s of the event 3.0, typical (sd) elsewhere 0.36
Hanford   : matched-filter SNR peaks at  18.6 at GPS 1126259462.4395; median elsewhere 1.15, max elsewhere 4.57
Livingston: matched-filter SNR peaks at  13.2 at GPS 1126259462.4324; median elsewhere 1.15, max elsewhere 4.29
arrival-time difference Hanford - Livingston: +7.1 ms (light travel time between the sites: 10 ms)
-0.1 s+0.0 s+0.1 sHanfordLivingston (shifted 7.1 ms, inverted)whitened strain05101520-0.4 s-0.2 s+0.0 s+0.2 s+0.4 smatched-filter SNR
Top: whitened and band-passed (35–350 Hz) strain at Hanford (rose) and Livingston (sky; shifted by 7.1 ms and inverted, because the detectors' arms are oriented differently), 0.17 s either side of the event: the chirp rising in frequency and amplitude until the merger is visible in both. Bottom: the matched-filter SNR in each detector around the event.

The noise's amplitude spectral density is 3.7×10⁻²³ per root hertz at 30 Hz but 8.0×10⁻²⁴ at 150 Hz: seismic noise below and quantum shot noise above leave a sensitive band between. In the raw data the event is invisible. After whitening and a 35–350 Hz band-pass, the Hanford trace near the event reaches 3.0, more than eight times its typical standard deviation (0.36) elsewhere, and the chirp is visible by eye. The matched filter is decisive: SNR 18.6 at Hanford and 13.2 at Livingston, never above 4.6 elsewhere in the 32 s. The peaks are 7.1 ms apart, Livingston first, within the 10 ms light-travel time between the sites. This agrees with the LIGO tutorial; the discovery paper's more careful analysis reported a combined SNR of 24.

The real analysis differs in three ways. The waveform depends on the masses and spins, so LIGO searches a template bank (about 250,000 templates for this search); we used one already known to fit. A high SNR is not yet a discovery: significance comes from the background, measured by sliding one detector's data against the other's by more than the 10 ms light-travel time, so no real signal can line up, and counting coincidences this strong. For GW150914 that is less than once in 200,000 years. And the detectors' arms point in different directions on the curved Earth, so their signals have nearly opposite signs, hence the inverted trace. The discovery paper reports arrival at Livingston 6.9 ms before Hanford, consistent with our 7.1 ms.

spot check 18.5

Why does the matched filter divide by the noise power spectral density, rather than simply correlating the raw data with the template?

Look at the Cauchy–Schwarz step in the proof: which inner product is being used?
In LIGO's data the noise at 30 Hz is about five times stronger in amplitude than at 150 Hz. Raw correlation would let the noisy low frequencies dominate; dividing by the PSD weights each frequency by how far it can be trusted, exactly the \(C^{-1}\) of the theorem.
Bayes — spectra as priors

By Bochner's theorem a stationary covariance function is the Fourier transform of a non-negative spectral density, so choosing a Gaussian-process kernel (Lecture 7) is choosing a prior spectrum. Wilson and Adams (2013) learn that spectrum as a mixture of Gaussians (Lecture 17a), with spectral-mixture kernels that discover and extrapolate periodicities such as the CO₂ annual cycle. Bretthorst (1988) showed that for a few sinusoids in noise the posterior for the frequencies is far sharper than the periodogram's resolution \(f_s/n\), with the periodogram arising as a sufficient statistic. LIGO's parameter estimation is Bayesian too: masses, spins, distance and sky position are sampled from a posterior whose likelihood is the noise-weighted inner product of Theorem 18.7.

quantum — the quantum Fourier transform and period finding

On \(m\) qubits, the quantum Fourier transform (QFT) maps the amplitudes \(x_0,\dots,x_{N-1}\) of a state, with \(N=2^m\), to their DFT (scaled to be unitary, with the opposite sign convention). The Cooley–Tukey factorisation of Theorem 18.2, applied qubit by qubit, gives \(O(m^2)\) gates, against \(O(N\log N)=O(m2^m)\) for the classical FFT. The catch: measurement returns one index \(k\) with probability \(|X_k|^2/N\), not the coefficients. Shor's algorithm (1994; SIAM Journal on Computing, 1997) needs only that: to factor \(M\) it applies the QFT to a superposition of the periodic function \(a^j\bmod M\), whose spectrum concentrates on multiples of \(N/r\), so a few samples reveal the period \(r\) and hence the factors. Period-finding is spectral analysis on amplitudes.

big picture — Fourier everywhere

4G, 5G and Wi-Fi send data on thousands of sub-carriers (orthogonal frequency-division multiplexing) separated by an FFT in every handset. MP3, AAC and JPEG transform short blocks into (modified or ordinary) discrete cosine coefficients and discard what the ear or eye barely notices. MRI scanners measure the body's Fourier transform and invert it by FFT. Radar, sonar, seismometers and radio telescopes rely on spectral analysis and matched filtering, and speech and audio models (Lecture 19) start from spectrograms.

history — a century-old prediction, heard

Albert Einstein predicted gravitational waves in 1916 and doubted they could be detected. Rainer Weiss designed a laser-interferometer detector, with its noise sources, in a 1972 MIT report; Kip Thorne and Ronald Drever built the theory and the Caltech prototype, and Barry Barish made LIGO a large international project from 1994. Matched filtering against relativity-computed templates was the planned search method for decades. GW150914 arrived during an engineering run, days before the first observing run, and was announced on 11 February 2016. The 2017 Nobel Prize in Physics went to Weiss, Barish and Thorne "for decisive contributions to the LIGO detector and the observation of gravitational waves"; Drever had died in March 2017.

9 — Summary, exercises, projects, reading

summary
exercises
  1. Compute by hand the DFT of \(x=(1,0,-1,0)\). Which frequency does it contain, and with what phase?

    Only \(x_0=1\) and \(x_2=-1\) are non-zero, so \(X_k=1-\omega^{2k}\) with \(\omega=e^{-2\pi i/4}=-i\) and \(\omega^{2k}=(-1)^k\). Hence \(X=(0,2,0,2)\).

    The non-zero coefficients are a conjugate pair at \(k=1\) and \(k=3=-1\), so by Theorem 18.1

    $$x_j=\tfrac14\big(2e^{2\pi ij/4}+2e^{-2\pi ij/4}\big)=\cos(\pi j/2):$$

    a cosine at one cycle per four samples, with phase 0 because \(X_1\) is real and positive.

  2. How many complex multiplications does the radix-2 FFT need for \(n=2^{20}\), roughly, compared with the matrix method? (Count \(n/2\) multiplications per level.)

    The FFT needs

    $$\tfrac n2\log_2n=2^{19}\times20\approx1.05\times10^7$$

    against \(n^2=2^{40}\approx1.1\times10^{12}\) for the matrix product: about 100,000 times fewer. At a billion multiplications per second, that is 0.01 s instead of 18 minutes.

  3. A moving average of length 3, \(y_k=(x_{k-1}+x_k+x_{k+1})/3\), is a filter. Find its frequency response \(H(f)\) and show that it is a (poor) low-pass filter that completely removes the frequency \(f_s/3\).

    The impulse response is \(1/3\) at lags \(-1,0,1\), so

    $$H(f)=\tfrac13\big(e^{2\pi if/f_s}+1+e^{-2\pi if/f_s}\big)=\tfrac13\big(1+2\cos(2\pi f/f_s)\big).$$

    It equals 1 at \(f=0\), falls to 0 at \(f=f_s/3\) (where \(\cos(2\pi/3)=-1/2\)), and rises again to \(-1/3\) at \(f_s/2\): frequencies near Nyquist are only reduced, and their sign is flipped. Better low-pass filters (Butterworth, windowed sinc) have a flat pass band and a monotone stop band.

  4. Explain why zero-padding a signal before the DFT (appending zeros to make it longer) gives a smoother-looking spectrum but does not improve the true frequency resolution.

    Zero-padding to length \(N\) evaluates the same function \(\sum_jx_je^{-2\pi ijf/f_s}\) (the discrete-time Fourier transform of the original \(n\) samples) at \(N\) frequencies instead of \(n\): it interpolates between bins. Two sinusoids closer than about \(f_s/n\) give overlapping peaks in that function whatever \(N\) is; only a longer record narrows the peaks.

  5. In Theorem 18.7 with white noise (\(C=\sigma^2I\)), show that the maximum SNR is \(\lVert s\rVert/\sigma\). What does this say about detecting a weak signal by making it longer?

    \(\sqrt{s^{\mathsf H}C^{-1}s}=\sqrt{\lVert s\rVert^2/\sigma^2}=\lVert s\rVert/\sigma\).

    For a signal of constant amplitude \(a\) lasting \(m\) samples, \(\lVert s\rVert=a\sqrt m\), so the SNR grows like \(\sqrt m\): a signal too weak to see in any single sample can be detected if it lasts long enough and its shape is known. This is why LIGO's long inspiral chirps, GPS signals buried below the thermal noise floor, and radar pulse-compression all work.

  6. (Code.) Run the matched filter of the LIGO code with the template time-reversed. What happens to the SNR peak, and why?

    Replace tc by tc[::-1]. The peak at the event collapses to the background level (single digits): a time-reversed chirp falls in frequency instead of rising, so it is nearly orthogonal to the real signal in the noise-weighted inner product. A matched filter rewards the specific shape, which is also why LIGO needs banks of hundreds of thousands of templates covering different masses and spins.

student projects

Each project uses this lecture's methods and public data, and has a clear result.

1. Rhythms of the city

question
What periodic rhythms (daily, weekly, annual) are visible in New York's 311 noise complaints or subway ridership, how strong is each, and how did they change after 2020?
data
NYC 311 Service Requests (complaint types beginning "Noise") aggregated hourly, 2015 to the present; MTA Subway Hourly Ridership (data.ny.gov) from 2020, and earlier turnstile counts.
method
Detrending; Welch spectra with confidence intervals; spectrograms over years to track how the weekly and daily peaks change; harmonic regression for the shapes of the cycles; comparison before and after March 2020.
outcome
A quantitative portrait of the city's rhythms and of how the pandemic and hybrid work reshaped them (for example a weaker weekday commuting peak and a stronger weekend cycle).

2. Heart-rate variability from public ECGs

question
How well do Fourier and wavelet methods measure heart-rate variability, and how do the standard low- and high-frequency HRV indices differ between healthy subjects and patients with arrhythmia?
data
PhysioNet's MIT-BIH Normal Sinus Rhythm and Arrhythmia databases (beat annotations give the RR-interval series).
method
RR series resampled evenly; Welch periodograms and Lomb–Scargle periodograms for uneven sampling; continuous wavelet transforms for time-varying HRV; the LF (0.04–0.15 Hz) and HF (0.15–0.4 Hz) powers with bootstrap intervals; sensitivity to window choices.
outcome
A comparison of HRV estimators with their uncertainties and a group comparison, of practical interest to anyone using wearable heart-rate data.

Reading and sources

Data. LIGO strain and template for GW150914: LIGO Open Science Center (GWOSC), CC BY 4.0, copies from github.com/losc-tutorial/LOSC_Event_tutorial. MIT-BIH record 100: PhysioNet (Open Data Commons Attribution licence), copy from github.com/MIT-LCP/wfdb-python sample data. Sunspots: SILSO, Royal Observatory of Belgium (CC BY-NC 4.0), via Rdatasets. Mauna Loa CO₂: NOAA Global Monitoring Laboratory and Scripps Institution of Oceanography, via github.com/datasets/co2-ppm. All were used in place of their original servers, which were not reachable from the build environment.

numbers in the text not printed by a code box are computed in verify_L18.py, figures and widget data in figs_L18.py; code-box outputs are pasted from actual runs (numpy, SciPy, PyWavelets, h5py and wfdb on one CPU core)