OTHER WAVELET TOPICS
This chapter contains a variety of topics of a more advanced nature that relate to wavelets. Since these topics are more advanced, an overview will be presented with details left to the various references.
7.1 COMPUTATIONAL COMPLEXITY
7.1.1 Wavelet Algorithm
In this section we briefly discuss the number of operations required to compute the wavelet decomposition of a signal (the computational complexity of the wavelet decomposition algorithm).
To take a concrete setting, suppose f is a continuous signal defined on the unit interval 0 ≤ t ≤ 1. Let
be a discrete sampling of ƒ. We wish to count the number of multiplications in the decomposition algorithm in terms of the number N = 2n.
Note that there are half as many aj-i coefficients as there are aj coefficients. So the index l on the left runs from 0 to 2j–
This result is often summarized by stating that the wavelet decomposition algorithm requires O(N) multiplication operations where N is the number of data at the top level. Here, O(N) stands for a number that is proportional to N. The ...