Informatics Report Series
Report
 EDI-INF-RR-0363
 Related Pages Report (by Number) Index Report (by Date) Index Author Index Institute Index Home
Title:Generalised Propagation for Fast Fourier Transforms with Partial or Missing Data
Authors: Amos Storkey
Date: 2004
Publication Title:Advances in Neural Information Processing Systems (NIPS2003)
Publisher:MIT Press
Publication Type:Conference Paper Publication Status:Published
Volume No:16
Abstract:
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 paper it is recognised that formulating the FFT algorithm as a belief network allows suitable priors to be set for the Fourier coefficients. Furthermore efficient generalised belief propagation methods between clusters of four nodes enable the Fourier coefficients to be inferred and the missing data to be estimated in near to ${\cal 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.