COMPLEXITY ANALYSIS OF WAVELET SIGNAL DECOMPOSITION AND RECONSTRUCTION

We give certain sequential and parallel algorithms and their computati onal analysis for signal decomposition and reconstruction based on wav elets. The signal decomposition (respectively, reconstruction) process is separated into two stages: The first is the preprocessing stage wh ere certain constants are computed for implementation to prepare for t he second stage in which signal decomposition (respectively, reconstru ction) is performed. In the decomposition (respectively, reconstructio n) stage, the input signal is transformed via different methods to com pute the output signal without changing the setup initialized in the p reprocessing 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 f inally illustrated for compactly supported spline-wavelets and are ana lyzed in detail in terms of the required arithmetic operations.