Generalised Propagation for Fast Fourier Transforms with Partial or Missing Data

Part of Advances in Neural Information Processing Systems 16 (NIPS 2003)

Bibtex Metadata Paper


Amos J. Storkey


Discrete Fourier transforms and other related Fourier methods have been practically implementable due to the fast Fourier transform (FFT). However there are many situations where doing fast Fourier transforms without complete data would be desirable. In this pa- per it is recognised that formulating the FFT algorithm as a belief network allows suitable priors to be set for the Fourier coe(cid:14)cients. Furthermore e(cid:14)cient generalised belief propagation methods be- tween clusters of four nodes enable the Fourier coe(cid:14)cients to be inferred and the missing data to be estimated in near to O(n log n) time, where n is the total of the given and missing data points. This method is compared with a number of common approaches such as setting missing data to zero or to interpolation. It is tested on generated data and for a Fourier analysis of a damaged audio signal.