approximation coefficients decomposed with high- and low-pass filters and then down-sampled. This is represented as a binary tree with nodes representing a sub-space with a different time-frequency localisation. The tree is known as a filter bank. At each level in the above diagram the signal is decomposed into low and high frequencies. Due to the decomposition process the input signal must be a multiple of where is the number of levels. For example a signal with 32 samples, frequency range 0 to and 3 levels of decomposition, 4 output scales are produced: Relationship to the mother wavelet The filterbank implementation of wavelets can be interpreted as computing the wavelet coefficients of a discrete set of child wavelets for a given mother wavelet . In the case of the discrete wavelet transform, the mother wavelet is shifted and scaled by powers of two where is the scale parameter and is the shift parameter, both which are integers. Recall that the wavelet coefficient of a signal is the projection of onto a wavelet, and let be a signal of length . In the case of a child wavelet in the discrete family above, Now fix at a particular scale, so that is a function of only. In light of the above equation, can be viewed as a convolution of with a dilated, reflected, and normalized version of the mother wavelet, , sampled at the points . But this is precisely what the detail coefficients give at level of the discrete wavelet transform. Therefore, for an appropriate choice of and , the detail coefficients of the filter bank correspond exactly to a wavelet coefficient of a discrete set of child wavelets for a given mother wavelet . As an example, consider the discrete Haar wavelet, whose mother wavelet is . Then the dilated, reflected, and normalized version of this wavelet is , which is, indeed, the highpass decomposition filter for the discrete Haar wavelet transform. Time complexity The filterbank implementation of the Discrete Wavelet Transform takes only O(N) in certain cases, as compared to O(N log N) for the fast Fourier transform. Note that if and are both a constant length (i.e. their length is independent of N), then and each take O(N) time. The wavelet filterbank does each of these two O(N) convolutions, then splits the signal into two branches of size N/2. But it only recursively splits the upper branch convolved