 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.