Fast Fourier Transform via Projections on Subspaces of a Multiresolution Analysis

Fast Fourier Transform (FFT) algorithms have been investigated since Cooley and Tukey published the first one in 1965. Most of them emphasize on the efficiency but not on the accuracy. In image analysis multiresolution representations are very effective for analyzing the information content of images. In the case of a function in ()RL2, these representations are given by its projections on the subspaces of a multiresolution analysis (MRA). And they approximate the function at a given resolution. In this work these multiresolution approximations are used to compute the discrete Fourier transform of some functions. By choosing the MRA associated with spaces of polynomial splines, and selecting the prope parameters, it is possible to achieve any prescribed accuracy. This method yields estimates of the computation errors in the FFT which are not available via any other approach