I have heard the DWT requires only N calculations. The documents I have read say it uses FIR filters so wouldn't this mean at each stage N*N calculations are required? Even if the signal is decimated at each stage how can you be using FIR filters (convolution) and not end up with a large number of calculations? The only thing that would reduce the calculations would be to use FFT convolution but that shouldnt be possible either since the purpose of the DWT is to avoid the FFT and the spectral leakage and the zero time resolution it brings. Has anyone implemented the DWT?

# Discrete Wavelet Transform

Started by ●January 14, 2009

Reply by ●January 14, 20092009-01-14

>I have heard the DWT requires only N calculations. The documents I have >read say it uses FIR filters so wouldn't this mean at each stage N*N >calculations are required? Even if the signal is decimated at each stage >how can you be using FIR filters (convolution) and not end up with alarge>number of calculations?The decimation and the filtering are combined (you don't compute samples which you'll through away). That's called polyphase filtering. And why N*N calculations? There are algorithms that computer the discrete wavelet transform in O(n) runtime. That means that the number of required calculations grows linearly with the number of input samples. If you say N*N, you seem to assume that the size of the fir filters grows with the amount of samples to process. The size of the wavelets (the fir filters) itself does not grow with the input-size. gr Bjoern>The only thing that would reduce the calculations would be to use FFT >convolution but that shouldnt be possible either since the purpose ofthe>DWT is to avoid the FFT and the spectral leakage and the zero time >resolution it brings. > >Has anyone implemented the DWT? > > >

Reply by ●January 15, 20092009-01-15

On Jan 15, 1:34�am, "TheMadScientist" <umutawa...@umassd.edu> wrote:> I have heard the DWT requires only N calculations. The documents I have > read say it uses FIR filters so wouldn't this mean at each stage N*N > calculations are required? Even if the signal is decimated at each stage > how can you be using FIR filters (convolution) and not end up with a large > number of calculations? > > The only thing that would reduce the calculations would be to use FFT > convolution but that shouldnt be possible either since the purpose of the > DWT is to avoid the FFT and the spectral leakage and the zero time > resolution it brings. > > Has anyone �implemented the DWT?Suppose you have a 1d signal, of length N. Suppose, for simplicity that N = 2^{n}. How many coefficients are there? At the first level there are 2^{n - 1}, then 2^{n - 2}, etc, until we reach the last level, where there is one (= 2^{n - n} wavelet coefficient and one scaling coefficient. *Naively*, to compute each coefficient takes an amount of time proportional to the size of the filter: for the first level, 2, the second 4, the third 8, and so on. So the time to compute each level is constant: 2^{n - m} coefficients each of which takes 2^ {m} time to compute. There are n levels. Then there is the scaling coefficient. So the total computation time is: T = n.2^{n} + n = O(n.2^{n}) = O(N log(N)) . This is naively. In practice, each level is computed from the scaling coefficients of the level before, so that the size of the filter in practice is always the same. This removes the log(N) factor from teh above, and gives a time complexity of O(N). Why don't you go look up discrete wavelet transform on wikipedia? illywhacker;