Discrete Wavelet Transform

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?

>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 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 of
the
>DWT is to avoid the FFT and the spectral leakage and the zero time
>resolution it brings.
>
>Has anyone  implemented the DWT?
>
>
>

On Jan 15, 1:34&#4294967295;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 &#4294967295;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;