Page "Fast Fourier transform" Paragraph 26

All of the FFT algorithms discussed below compute the DFT exactly ( in exact arithmetic, i. e. neglecting floating-point errors ).

A few " FFT " algorithms have been proposed, however, that compute the DFT approximately, with an error that can be made arbitrarily small at the expense of increased computations.

Such algorithms trade the approximation error for increased speed or other properties.

For example, an approximate FFT algorithm by Edelman et al.

( 1999 ) achieves lower communication requirements for parallel computing with the help of a fast multipole method.

A wavelet-based approximate FFT by Guo and Burrus ( 1996 ) takes sparse inputs / outputs ( time / frequency localization ) into account more efficiently than is possible with an exact FFT.

Another algorithm for approximate computation of a subset of the DFT outputs is due to Shentov et al.

( 1995 ).

The Edelman algorithm works equally well for sparse and non-sparse data, since it is based on the compressibility ( rank deficiency ) of the Fourier matrix itself rather than the compressibility ( sparsity ) of the data.

Conversely, if the data are sparse — that is, if only K out of N Fourier coefficients are nonzero — then the complexity can be reduced to O ( K log N log ( N / K )), and this has been demonstrated to lead to practical speedups compared to an ordinary FFT for N / K > 32 in a large-N example ( N = 2 < sup > 22 </ sup >) using a probabilistic approximate algorithm ( which estimates the largest K coefficients to several decimal places ).