Wavelets

Wavelets provide time-frequency analysis — localizing both time and frequency information simultaneously. Unlike the STFT (fixed window), wavelets use a variable-resolution approach: narrow windows for high frequencies, wide windows for low frequencies.

Continuous Wavelet Transform (CWT)

CWT{x}(a, b) = (1/√a) ∫ x(t) · ψ*((t-b)/a) dt

a: Scale (inversely proportional to frequency). Large a → low frequency. Small a → high frequency.

b: Translation (time position).

ψ(t): Mother wavelet — a localized, oscillating function with zero mean.

Discrete Wavelet Transform (DWT)

Sample the CWT at dyadic scales a = 2ʲ and translations b = k·2ʲ:

DWT{x}(j, k) = Σₙ x[n] · ψ_{j,k}[n]

Multiresolution Analysis (MRA)

Decompose a signal into approximation (low-frequency) and detail (high-frequency) components at multiple scales.

Signal x[n]
   ↓
[LPF h₀] → ↓2 → Approximation a₁[n]  →  [LPF h₀] → ↓2 → a₂[n] → ...
[HPF h₁] → ↓2 → Detail d₁[n]          →  [HPF h₁] → ↓2 → d₂[n] → ...

At each level: low-pass filter (scaling function) → downsample → approximation. High-pass filter (wavelet) → downsample → detail.

Reconstruction: Upsample → filter → add. If the filters satisfy the perfect reconstruction condition, the original signal is exactly recovered.

Scaling Function and Wavelet

Scaling function φ(t): Low-pass. Captures the approximation (smooth) part.

Wavelet function ψ(t): High-pass (band-pass). Captures the detail (fluctuation) part.

Two-scale relation: φ(t) = √2 Σ h₀[k] φ(2t - k). The scaling function is defined recursively in terms of itself at finer scale.

Wavelet Families

| Family | Properties | Use | |---|---|---| | Haar | Simplest. Piecewise constant. Discontinuous. | Education, simple analysis | | Daubechies (dbN) | Compact support. N vanishing moments. Smooth. | General signal processing | | Coiflets | Nearly symmetric Daubechies. Both φ and ψ have vanishing moments. | Numerical analysis | | Symlets | Near-symmetric modification of Daubechies. | When symmetry matters | | Morlet | Gaussian modulated complex sinusoid. No compact support. | Time-frequency analysis, CWT | | Mexican Hat | Second derivative of Gaussian. | Edge detection, physics |

Vanishing moments: A wavelet with N vanishing moments (∫tᵏψ(t)dt = 0 for k = 0,...,N-1) is orthogonal to polynomials of degree < N. Better at representing smooth signals — detail coefficients are small for smooth regions.

Filter Bank Implementation

The DWT is efficiently computed as a filter bank (cascade of filters + downsamplers).

PROCEDURE DWT_LEVEL(signal, lpf, hpf)
    approx ← CONVOLVE_DOWNSAMPLE(signal, lpf)
    detail ← CONVOLVE_DOWNSAMPLE(signal, hpf)
    RETURN (approx, detail)

PROCEDURE DWT(signal, lpf, hpf, levels)
    approx ← COPY(signal)
    details ← empty list
    FOR i ← 1 TO levels DO
        (a, d) ← DWT_LEVEL(approx, lpf, hpf)
        APPEND d TO details
        approx ← a
    RETURN (approx, details)  // final approximation + all detail levels

Computation: O(N) per level × O(log N) levels = O(N) total. Faster than FFT!

Wavelet Packets

Generalization: decompose both approximation and detail at each level (not just approximation). Creates a full binary tree of subbands. More flexible frequency decomposition — choose the best tree based on an entropy criterion (best basis algorithm).

Applications

Denoising

1. Compute DWT of noisy signal.
2. Threshold small detail coefficients (set to zero if below threshold — hard thresholding, or shrink toward zero — soft thresholding).
3. Reconstruct via inverse DWT.

Why it works: Signal energy concentrates in a few large coefficients. Noise energy spreads evenly across all coefficients. Thresholding removes noise without significantly affecting the signal.

Compression

JPEG 2000: Uses the biorthogonal CDF 9/7 wavelet (lossy) or CDF 5/3 (lossless). Better quality than JPEG at the same file size, especially at low bit rates. Supports progressive decoding.

EZW, SPIHT, EBCOT: Wavelet-based image compression algorithms. Exploit the tree structure of wavelet coefficients (parent-child relationships across scales).

Feature Extraction

Extract time-frequency features at multiple scales for pattern recognition.

ECG analysis: QRS complex detection, arrhythmia classification using wavelet features.

Texture analysis: Wavelet subbands capture texture information at different scales and orientations.

Edge Detection

Wavelet transform maxima correspond to edges (abrupt changes) at different scales. Multi-scale edge detection is more robust than single-scale methods (Canny).

Applications in CS

• Image compression: JPEG 2000, ICER (used by Mars rovers).
• Audio compression: MPEG-4 AAC uses MDCT (related to wavelets for time-frequency analysis).
• Signal denoising: Remove noise while preserving signal features.
• Anomaly detection: Detect unusual patterns at multiple time scales.
• Financial analysis: Multi-scale trend analysis in time series.
• Numerical analysis: Wavelet-based methods for PDEs (adaptive resolution where needed).