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)
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.
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\).)
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.
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.
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.
# 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.
A signal is recorded for 2 seconds at 100 samples per second. How far apart, in hertz, are the DFT's frequency bins?
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.
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.
Let \(x(t)\) contain no frequencies at or above \(B\) hertz.
(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.
# 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).
A 70 Hz tone is sampled at 100 Hz without an anti-aliasing filter. At what frequency (in Hz) does it appear?
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).
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.
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.
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.
# 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).
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.
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.
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.
# 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.
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.
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.
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?
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.
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.
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.
# 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.
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?
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.
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.
# 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.
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.
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.
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).
# 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)
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.
Why does the matched filter divide by the noise power spectral density, rather than simply correlating the raw data with the template?
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.
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.
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.
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.
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.
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.
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.
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.
\(\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.
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.
Each project uses this lecture's methods and public data, and has a clear result.
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)