The Fast Wavelet Transform

The Fast Wavelet Transform (FWT) is a computationally efficient method for implementing the Discrete Wavelet Transform (DWT). It reduces the complexity of calculating the wavelet coefficients at different scales by taking advantage of the relationship between adjacent scales. In contrast to direct computation of the wavelet transform, which can be slow and resource-intensive, FWT allows for a faster approach with fewer calculations.

Key Mathematical Concepts in FWT:

1. Wavelet Transform Overview

A wavelet transform breaks down a signal into components at various scales and resolutions. It is based on a fundamental function called the wavelet function $\psi(x)$, and an accompanying scaling function $\phi(x)$. The signal is decomposed into a set of coefficients at different scales and positions using these functions.

• Scaling function $\phi(x)$: Represents the low-frequency, or approximation, components of the signal.
• Wavelet function $\psi(x)$: Represents the high-frequency, or detail, components of the signal.

2. Multiresolution Analysis (MRA)

Multiresolution analysis is at the heart of the wavelet transform. The goal of MRA is to represent a signal at multiple levels of resolution. At each level, the signal is decomposed into:

• Approximation coefficients (low-frequency components).
• Detail coefficients (high-frequency components).

This decomposition continues down through different scales until the desired level of detail is reached.

3. FWT and Subband Coding

The FWT can be viewed as a type of subband coding system. A signal is passed through a series of filters to separate it into different subbands:

• Low-pass filter (scaling) for approximations.
• High-pass filter (wavelet) for details.

Each filtering operation is followed by downsampling, which means reducing the resolution of the signal by keeping every second sample. This process is repeated across multiple levels (scales), yielding a pyramid-like structure.

Fast Wavelet Transform Mathematical Formulation:

The Refinement Equation

The FWT is built on the idea of scaling the wavelet and scaling functions. The refinement equation expresses the wavelet function as a sum of shifted versions of itself at a coarser scale.

For the scaling function $\phi(x)$:

For the wavelet function $\psi(x)$:

Here, $h[n]$ and $g[n]$ are filter coefficients for the scaling and wavelet functions, respectively.

Fast Wavelet Transform Steps:

1. Decomposition (Analysis Stage)

   • The input signal $f(x)$ is passed through two filters: a low-pass filter (associated with the scaling function) and a high-pass filter (associated with the wavelet function).
   • After filtering, the signal is downsampled by keeping only every second sample, effectively reducing the signal size by half.
   • This process is repeated iteratively for the low-pass filtered signal to achieve multiple levels of decomposition.

   Mathematically, the approximation and detail coefficients at level $j$ are given by:

   $$c_j[k] = \sum_{n} h[n – 2k] c_{j+1}[n] \quad \text{(approximation coefficients)}$$ $$d_j[k] = \sum_{n} g[n – 2k] c_{j+1}[n] \quad \text{(detail coefficients)}$$

2. Reconstruction (Synthesis Stage)

   • To reconstruct the signal, the approximation and detail coefficients are upsampled and passed through the corresponding filters.
   • The results are then combined to reconstruct the signal at the previous resolution.

   Mathematically, the reconstruction of the signal is performed using:

   $$c_{j+1}[n] = \sum_{k} h[n – 2k] c_j[k] + \sum_{k} g[n – 2k] d_j[k]$$

This process ensures that the original signal can be perfectly reconstructed from its wavelet coefficients.

Example: Haar Wavelet FWT

Let’s consider the Haar wavelet for a simple example. The Haar wavelet is the simplest wavelet and is represented by step functions. It has the following properties:

• Scaling coefficients: $h[n] = [\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}]$
• Wavelet coefficients: $g[n] = [\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}}]$

Let’s take an example signal $f(x) = [1, 4, -3, 0]$.

Step 1: Decomposition

• Apply the low-pass filter (scaling function):

  $$c_1 = \frac{1}{\sqrt{2}}(1 \cdot 1 + 4 \cdot 1) = 3.54, \quad c_2 = \frac{1}{\sqrt{2}}(-3 \cdot 1 + 0 \cdot 1) = -2.12$$

  So, the approximation coefficients at this level are $c_1 = [3.54, -2.12]$.

• Apply the high-pass filter (wavelet function):

  $$d_1 = \frac{1}{\sqrt{2}}(1 \cdot 1 – 4 \cdot 1) = -2.12, \quad d_2 = \frac{1}{\sqrt{2}}(-3 \cdot 1 – 0 \cdot 1) = 1.41$$

  So, the detail coefficients at this level are $d_1 = [-2.12, 1.41]$.

This process can be repeated for the approximation coefficients to further decompose the signal.

Step 2: Reconstruction

• To reconstruct the signal, we combine the approximation and detail coefficients using the inverse of the filters and upsampling.

• Using the previously calculated coefficients $c_1 = [3.54, -2.12]$ and $d_1 = [-2.12, 1.41]$, we apply the reconstruction formula:

  $$f(x) = \frac{1}{\sqrt{2}}(3.54 \cdot 1 + -2.12 \cdot 1)$$

  This leads to a reconstructed signal that closely matches the original $f(x) = [1, 4, -3, 0]$.

Advantages of FWT:

1. Computational Efficiency: The FWT reduces the number of mathematical operations from $O(N^2)$ to $O(N)$, making it suitable for large-scale data processing, such as image or signal processing.
2. Multiresolution Analysis: FWT offers a natural way to analyze a signal at different levels of detail. This is useful in applications like image compression and denoising.
3. Perfect Reconstruction: The FWT allows for perfect reconstruction of the original signal from its wavelet coefficients.

Applications:

• Image Compression: JPEG 2000 uses the FWT to compress images by retaining only the significant wavelet coefficients and discarding the rest.
• Signal Denoising: FWT can be used to remove noise from signals by thresholding the detail coefficients.
• Time-Frequency Analysis: FWT is widely used for analyzing signals that change over time, such as speech signals and seismic data.