Lably
Skip to content

Discrete wavelet transform

Transform in numerical harmonic analysis

  • 17 min read
  • 5 chapters

Related on Lably

Through Numerical analysis, Convolution and Binary tree

Lab · Class 6–12AI & Python Builds (Medha AI)Lab · Class 10–12Pixel Art ExplorerLab · Class 10–12Handwriting RecognizerLab · Class 8–12AR Marker Tracking

Definition

One level of the transform

The DWT of a signal x is calculated by passing it through a series of filters. First the samples are passed through a low-pass filter with impulse response g resulting in a convolution of the two:

y[n]=(x∗g)[n]=∑k=−∞∞x[k]g[n−k]

The signal is also decomposed simultaneously using a high-pass filter h. The outputs give the detail coefficients (from the high-pass filter) and approximation coefficients (from the low-pass). It is important that the two filters are related to each other and they are known as a quadrature mirror filter.

However, since half the frequencies of the signal have now been removed, half the samples can be discarded according to Nyquist's rule. The filter output of the low-pass filter g in the diagram above is then subsampled by 2 and further processed by passing it again through a new low-pass filter g and a high- pass filter h with half the cut-off frequency of the previous one, i.e.:

ylow[n]=∑k=−∞∞x[k]g[2n−k]
yhigh[n]=∑k=−∞∞x[k]h[2n−k]

This decomposition has halved the time resolution since only half of each filter output characterises the signal. However, each output has half the frequency band of the input, so the frequency resolution has been doubled.

With the subsampling operator ↓

(y↓k)[n]=y[kn]

the above summation can be written more concisely.

ylow=(x∗g)↓2
yhigh=(x∗h)↓2

However computing a complete convolution x∗g with subsequent downsampling would waste computation time.

The Lifting scheme is an optimization where these two computations are interleaved.

Cascading and filter banks

This decomposition is repeated to further increase the frequency resolution and the approximation coefficients decomposed with high- and low-pass filters and then down-sampled. This is represented as a binary tree with nodes representing a sub-space with a different time-frequency localisation. The tree is known as a filter bank.

At each level in the above diagram the signal is decomposed into low and high frequencies. Due to the decomposition process the input signal must be a multiple of 2n where n is the number of levels.

For example a signal with 32 samples, frequency range 0 to fn and 3 levels of decomposition, 4 output scales are produced:

Relationship to the mother wavelet

The filterbank implementation of wavelets can be interpreted as computing the wavelet coefficients of a discrete set of child wavelets for a given mother wavelet ψ(t). In the case of the discrete wavelet transform, the mother wavelet is shifted and scaled by powers of two

ψj,k(t)=12jψ(t−k2j2j)

where j is the scale parameter and k is the shift parameter, both of which are integers.

Recall that the wavelet coefficient γ of a signal x(t) is the projection of x(t) onto a wavelet, and let x(t) be a signal of length 2N. In the case of a child wavelet in the discrete family above,

γjk=∫−∞∞x(t)12jψ(t−k2j2j)dt

Now fix j at a particular scale, so that γjk is a function of k only. In light of the above equation, γjk can be viewed as a convolution of x(t) with a dilated, reflected, and normalized version of the mother wavelet, h(t)=12jψ(−t2j), sampled at the points 1,2j,2⋅2j,...,2N. But this is precisely what the detail coefficients give at level j of the discrete wavelet transform. Therefore, for an appropriate choice of h[n] and g[n], the detail coefficients of the filter bank correspond exactly to a wavelet coefficient of a discrete set of child wavelets for a given mother wavelet ψ(t).

As an example, consider the discrete Haar wavelet, whose mother wavelet is ψ=[1,−1]. Then the dilated, reflected, and normalized version of this wavelet is h[n]=12[−1,1], which is, indeed, the highpass decomposition filter for the discrete Haar wavelet transform.

Time complexity

The filterbank implementation of the Discrete Wavelet Transform takes only O(N) in certain cases, as compared to O(N log N) for the fast Fourier transform.

Note that if g[n] and h[n] are both a constant length (i.e. their length is independent of N), then x∗h and x∗g each take O(N) time. The wavelet filterbank does each of these two O(N) convolutions, then splits the signal into two branches of size N/2. But it only recursively splits the upper branch convolved with g[n] (as contrasted with the FFT, which recursively splits both the upper branch and the lower branch). This leads to the following recurrence relation

T(N)=2N+T(N2)

which leads to an O(N) time for the entire operation, as can be shown by a geometric series expansion of the above relation.

As an example, the discrete Haar wavelet transform is linear, since in that case h[n] and g[n] are constant length 2.

h[n]=[−22,22]g[n]=[22,22]

The locality of wavelets, coupled with the O(N) complexity, guarantees that the transform can be computed online (on a streaming basis). This property is in sharp contrast to FFT, which requires access to the entire signal at once. It also applies to the multi-scale transform and also to the multi-dimensional transforms (e.g., 2-D DWT).

Sign in to keep reading

4 more chapters are free with a Lably account.

More in Topics in mathematics

DiameterStraight line segment that passes through the centre of a circleSmoothnessDegree of differentiability of a function or mapGroup actionTransformations induced by a mathematical groupMonotonic functionOrder-preserving mathematical functionCountable setMathematical set that can be enumeratedEllipsoidQuadric surface that looks like a deformed sphere