Trigonometry
Wavelets and Multiresolution Analysis
Цели урока
- Understand the MRA structure and the role of nested subspaces
- Apply the Mallat algorithm for DWT in O(N) operations
- Choose a wavelet family based on signal properties
- Interpret CWT time-scale maps
Предварительные знания
- Fourier Series
- Fourier Transform
- L^2 spaces
How can one see 'where exactly in a signal' an event occurs - something Fourier is blind to by definition?
- JPEG 2000: medical imaging compression 47x (ISO 15444 standard)
- Seismology: detecting non-stationary seismic waves via time-scale analysis
- ECG analysis: detecting time-domain patterns in heart rhythm
- Audio denoising: threshold processing of wavelet coefficients
History: from Haar to Daubechies
Haar described the first wavelet in 1910 - a simple step function. Until the 1980s, no one knew how to build smooth orthogonal wavelets with compact support. Jean Morlet in 1982 applied scalable wave packets in geophysics. Yves Meyer in 1985 built the first smooth orthogonal wavelet. Stephane Mallat in 1989 formulated MRA and the O(N) fast algorithm. Ingrid Daubechies in 1988 constructed the dbN family - which became the engineering standard.
Multiresolution Analysis (MRA)
JPEG 2000 compresses hospital MRI scans 47-fold without losing diagnostically critical detail. The method relies on Daubechies D8 wavelets, which capture local frequency content simultaneously in space and scale. Unlike Fourier analysis, a wavelet can answer not only 'at what frequency' but also 'where exactly in the signal' an event occurs.
Key difference from Fourier: wavelet psi_{j,k}(t) = 2^{j/2} psi(2^j t - k) is localized in both time (shift k) and frequency (scale j). A Fourier harmonic e^{i*xi*t} is spread over the entire axis.
What is the computational complexity of the Mallat DWT decomposition?
At each level, O(N) convolution + downsampling by 2. Levels: O(log N). Total: N + N/2 + N/4 + ... = 2N. So O(N) overall - faster than FFT's O(N log N).
Wavelet Families and Their Properties
The Haar wavelet existed since 1910, but a family of practically useful smooth wavelets with compact support was built by Ingrid Daubechies in 1988. The key insight: a wavelet with N vanishing moments exactly represents polynomials of degree up to N-1, and that is precisely the property needed for efficient compression of smooth image regions.
| Wavelet | Vanishing moments | Filter length | Application |
|---|---|---|---|
| Haar | 1 | 2 | Threshold processing, simplicity |
| Daubechies D4 | 2 | 4 | Image compression |
| Daubechies D8 | 4 | 8 | JPEG 2000, medical imaging |
| Symlet S8 | 4 | 8 | Denoising (more symmetric) |
| Biorthogonal 9/7 | 4/4 | 9+7 | JPEG 2000 ISO standard |
What does the condition of N vanishing moments mean for compression?
The condition int t^k psi(t) dt = 0 means <psi, p> = 0 for any polynomial p of degree <= N-1. Smooth (locally polynomial) parts of the signal are invisible to the wavelet - zero coefficients, efficient compression.
Continuous Wavelet Transform and Time-Scale Analysis
NASA seismologists detected moonquakes via Apollo sensors in 1969 using analysis equivalent to the CWT. A signal lasting hours with changing frequency - standard Fourier is blind to such non-stationarity. The CWT builds an amplitude map in (scale, time) coordinates: one can see how one frequency gradually transitions into another.
CWT is redundant (a continuum of functions for an L^2 signal), so in practice it is discretized on an octave grid: a = 2^j and b = k*2^j.
What is the principal advantage of the CWT over the Fourier transform for non-stationary signals?
Fourier gives a global spectrum - losing information about when components occur. CWT builds a scale-time map W(a,b): one can see when and at what scale a feature appears. The variable resolution respects the Heisenberg uncertainty principle.
Connections to other topics
Wavelets unite functional analysis, filter theory, and signal processing
- MRA and L^2 — Related topic
- Digital filter banks — Related topic
- Sparse representations — Related topic
- Scattering transform — Related topic
Итоги
- MRA defines nested subspaces V_j with orthogonal complements W_j generated by the wavelet psi
- Mallat's algorithm performs DWT in O(N) via a low/high-pass filter bank with downsampling at each level
- N vanishing moments make wavelet coefficients zero on smooth signal regions - the key to compression
- CWT provides variable time-frequency resolution with the Heisenberg principle: better time resolution at high frequencies, better frequency resolution at low
Вопросы для размышления
- Why must a wavelet necessarily have zero mean (the zeroth vanishing moment)?
- How does one choose a wavelet family for a specific task - compression vs. feature detection?
- What is the trade-off between time and frequency resolution when choosing the scale in CWT?
Связанные уроки
- trig-21 — Fourier series provide the foundation for MRA theory
- trig-25-dct — DCT is a global transform; DWT adds time localization
- trig-28 — Harmonic analysis formalizes the L^2 theory of wavelets