Complexity Analysis of Wavelet Signal Decomposition and Reconstruction

We give certain sequential and parallel algorithms and their computational analysis for signal decomposition and reconstruction based on wavelets. The signal decomposition (respectively, reconstruction) process is separated into two stages: The first is the preprocessing stage where certain constants are computed for implementation to prepare for the second stage in which signal decomposition (respectively, reconstruction) is performed. In the decomposition (respectively, reconstruction) stage, the input signal is transformed via different methods to compute the output signal without changing the setup initialized in the preprocessing stage. We describe certain sequential algorithms for both the preprocessing and the decomposition (respectively, reconstruction) stages, and parallel algorithms for the latter. The algorithms are finally illustrated for compactly supported spline-wavelets and are analyzed in detail in terms of the required arithmetic operations. © 1994 IEEE