Number of datapoints after decimation in discrete wavelet wavelet analysis

Question

I am following an example provided by MATLAB on 1-D wavelet decomposition (DWT). The number of datapoints is 10000. If we do a level 3 decomposition following a similar example provided by MATLAB using https://www.mathworks.com/help/wavelet/ref/wavedec.html

The length of the coefficients "l" after wavelet decomposition is

[127 127 252 501 1000], corresponding to the length of approximation coefficients at level 3, number of detail coefficients at level 3, number of details coefficients at level 2 and number of detail coefficients at level 1. Why are these numbers not exactly divided by 2?

For example, 1000/2 = 500, it is 501. Similarly at next level 500/2 should be 250 but it is 252 and at the third level 250/2 should be 125 but it is 127.

Secondly, every textbook says that DWT needs 2^n data points. Even if we choose a number such as 8192, the number of decimated coefficients are not exactly and successively divided by 2. What is the reason behind this?

Thanks.

Answer 1

As with Fourier, as with IIR filtering, discrete wavelet forward implementation, and how they can be inversed, depends of lot on how you treat the samples that you don't know, for standard finite support data. In other words: as you convolve, what do you do on the left side and the right side of the signal.

There is a huge literature on how to perform a non-expansive decomposition, that generates the same number of coefficients that the number of samples. But yo can see the constraints easily: when I have 3 samples, how to subsample this evenly into a low-pass and a high-pass series?

To made a long story short, if the signal length can be divided by $2^L$, $L$ wavelet levels can be obtained in general with the appropriate signal extension, governed by Matlab's dwtmode: "the options The DWT associated with the symmetric, smooth, zero, and periodic extension modes are slightly redundant." This is generally due to how wavelet filters overlap where the signal is not defined. This is related to the convolution with lowpass and highpass filters as well, before decimation. And convolution tends to increase the signal's length. A filter with support $K$ convolved with a signal of length $N$ generally yields a filtered signal of length $N+K-1$. So if you decimate and when to keep all necessary information, you need to keep a little more coefficients at each level. There are nice description in Chapter 4 of "Wavelets in chemistry", Beata Walczak, 2000.

However in some case, like with the Haar wavelet, or as detailed in C. Brislawn, 1996 Classification of Nonexpansive Symmetric Extension Transforms for Multirate Filter Banks, nonexpansive schemes can be designed.

In practice, people who really want to be nonexpansive uses modified DWT algorithms, like the lifting scheme, or wavelets on the interval, that are not 100% pure discrete wavelet transforms.