0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. I am a chemist and find wavelets an interesting area. My understanding of decimation was that the data gets reduced by half at every level. So if we wish to decompose 1000 data points by level =3, i.e., 2^3, so the level should have 1000/8 = 125. MATLAB shows 127, that is what I wanted to confirm why this is happening? $\endgroup$ – M. Farooq Dec 11 '19 at 17:35
  • $\begingroup$ There is decimation, but there is convolution with 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 $\endgroup$ – Laurent Duval Dec 11 '19 at 19:15
  • $\begingroup$ I have also added a reference to the book "Wavelets in chemistry" $\endgroup$ – Laurent Duval Dec 11 '19 at 19:19
  • $\begingroup$ Thanks. I guess that makes with the numbers. As per MATLAB, coif2 has 12 support points. I had a data of 12050. After convolution, we will have 12050+12-1= 12061. If I divide that by 2, I get 6030, which is the number of coefficients I get after doing a single level decomposition. So it seems MATLABS does not discard the edge points after convolution. I had asked this on Mathworks, but nobody answered. mathworks.com/matlabcentral/answers/… $\endgroup$ – M. Farooq Dec 11 '19 at 20:06
  • 1
    $\begingroup$ There are journals with less qualified reviewers for mathematics, and most people do not care about the little increase in size that is cancelled upon reconstruction, apart from coding and compression people, who what to save every bit of information. And $2^8=256$, so it seems ok here $\endgroup$ – Laurent Duval Dec 11 '19 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.