Fourier Analysis on Groups and Wavelets

Цели урока

• Understand Fourier analysis on locally compact abelian groups via characters and Haar measure
• Know Pontryagin duality and the Fourier transform on R, Z, T, and Z/N
• Understand the wavelet transform as time-frequency localization beyond classical Fourier
• See spectral methods in ML (FNO, spectral GNNs) as applications of group-theoretic Fourier analysis

Предварительные знания

• Differential forms
• Integration on manifolds
• Fourier series

• Differential Forms

Why does every digital audio file, wireless signal, and image compression algorithm trace back to one theorem about abstract groups?

• 5G OFDM: FFT on Z/N simultaneously modulates 6600 subcarriers per symbol - Pontryagin duality for Z/N at 100 MHz
• JPEG 2000: Daubechies wavelets compress images 20:1 vs JPEG's 10:1 - wavelet transform outperforms DCT for high compression
• FNO neural PDE solver: FFT + learned frequency filter achieves 1000x speedup over numerical solvers for Navier-Stokes
• AlphaFold2 structure module: SE(3)-equivariant operations exploit Haar measure on the rotation group SO(3)

Pontryagin, Haar, and the abstraction of Fourier

Alfred Haar proved the existence of invariant measures on compact groups in 1933. Lev Pontryagin (1908-1988) proved his duality theorem in 1934, generalizing Fourier inversion to all locally compact abelian groups. Andre Weil extended Haar measure to all locally compact groups in 1940. Jean Morlet developed continuous wavelets in 1982 for geophysical applications; Ingrid Daubechies (1992) constructed the compactly supported wavelets used in JPEG 2000. The same abstract structure - Fourier analysis on groups - now runs in every smartphone, satellite, and medical scanner on Earth.

Fourier Analysis on Groups

Lev Pontryagin proved in 1934 that for any locally compact abelian group G, its character group G-hat satisfies G-hat-hat = G. This explains Fourier invertibility: on R, R-hat = R. The DFT on Z/N runs in O(N log N) via FFT. Every digital audio codec, image compressor, and wireless protocol runs on this theorem. JPEG 2000 uses FFT on Z/N. 5G radio uses FFT for OFDM modulation - 200 carriers simultaneously.

Four canonical examples: G=R: classical Fourier, G-hat=R. G=Z/N: DFT, G-hat=Z/N (self-dual). G=T (circle): Fourier series, G-hat=Z. G=Z: z-transform, G-hat=T. Each one is Fourier on a different group, all unified by Pontryagin duality.

Haar Measure and Invariant Integration

Every locally compact group G has a unique (up to scalar) left-translation-invariant measure: the Haar measure. For R: Lebesgue. For Z: counting. For T (circle): arc length. For GL(n,R): the measure d mu = dA / |det A|^n (not Lebesgue!). Haar measure is what makes the Fourier transform work on groups: translation-invariance ensures characters are orthogonal.

For compact groups G: the dual G-hat consists of irreducible unitary representations (not just characters for non-abelian G). The Peter-Weyl theorem generalizes Fourier series: L^2(G) = sum_{rho in G-hat} (dim rho)^2 representations.

Wavelet Analysis and Multiresolution

Fourier analysis has one weakness: a single frequency component is spread over all time. A spike at t=5 contributes to every frequency. Wavelets fix this: the mother wavelet psi is localized in both time and frequency. Jean Morlet proposed wavelets in 1982 for seismic analysis. JPEG 2000 uses Daubechies 9/7 wavelets - achieving 20:1 compression far beyond JPEG's DCT-based 10:1. Transformers have an analog: attention is a learned, data-dependent wavelet-like decomposition.

Spectral Methods in Machine Learning

Fourier Neural Operator (FNO, Anandkumar et al. 2021): applies FFT, learns a filter in frequency space, applies inverse FFT. One pass on a 64x64 grid: thousands of FFT operations. Achieves 1000x speedup over numerical PDE solvers for Navier-Stokes. The mathematical foundation: convolution theorem - F(f * g) = F(f) * F(g). Learned in frequency space = learned global convolution in space.

Spectral Graph Neural Networks (ChebNet, GCN) use eigendecomposition of the graph Laplacian L = U Lambda U^T as the 'Fourier' for graphs. Graph convolution: g * x = U (g(Lambda) . (U^T x)). This is Fourier analysis on the discrete graph - the characters are eigenvectors of L rather than exp(i xi x). The Pontryagin duality for groups generalizes to spectral theory on arbitrary graphs.

Attention mechanism in Transformers is related to wavelets: each head learns a soft localized query-key matching, functioning as a data-dependent filter bank. Some interpretability work (e.g., Olah et al.) shows early attention heads learning low-frequency (global) patterns, later heads high-frequency (local) patterns - multiresolution structure.

Connections to other topics

Fourier analysis on groups unifies signal processing, representation theory, and machine learning on structured data.

• Signal processing — Related topic
• Spectral GNNs — Related topic
• Representation theory — Related topic
• Quantum mechanics — Related topic

Итоги

• Pontryagin duality: for locally compact abelian G, G-hat-hat = G; Fourier on G = expansion in characters chi: G -> T
• Haar measure: unique translation-invariant measure on G; orthogonality of characters follows from translation-invariance
• Examples: G=R (Lebesgue, classical Fourier), G=Z/N (counting, DFT+FFT), G=T (arc length, Fourier series)
• Wavelets: simultaneous time-frequency localization; zero-mean condition ensures admissibility; DWT runs in O(N)
• FNO: Fourier in frequency space + learned filter + IFFT = learned global convolution; 1000x PDE speedup

Вопросы для размышления

• Pontryagin duality says G-hat-hat = G. What does this mean physically for Heisenberg's uncertainty principle - position and momentum are Fourier duals?
• Wavelets localize in both time and frequency, unlike Fourier which is global. In what sense is the attention mechanism in Transformers a learned, data-dependent analog of wavelets?
• The graph Laplacian L plays the role of d^2 in discrete geometry. What would a 'graph de Rham cohomology' look like - and what topological information would it encode?

Связанные уроки

• calc-27-diff-forms — Differential forms and exterior calculus underlie spectral theory on manifolds
• calc-29-distributions — Fourier transform on tempered distributions is the rigorous framework
• calc-28-manifold-int — Integration on groups uses the Haar measure framework