Generalised propagation for fast Fourier transforms with partial or missing data

AJ Storkey

Generalised propagation for fast Fourier transforms with partial or missing data

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 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.

Original language	English
Title of host publication	ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 16
Subtitle of host publication	Proceedings of the 2003 Conference
Editors	S Thrun, K Saul, B Scholkopf
Place of Publication	CAMBRIDGE
Publisher	MIT Press
Pages	433-440
Number of pages	8
ISBN (Print)	0-262-20152-6
Publication status	Published - 2004
Event	17th Annual Conference on Neural Information Processing Systems (NIPS) - , Canada Duration: 8 Dec 2003 → …

Publication series

Name	ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS
Publisher	M I T PRESS
Volume	16
ISSN (Print)	1049-5258

Conference

Conference	17th Annual Conference on Neural Information Processing Systems (NIPS)
Country/Territory	Canada
Period	8/12/03 → …

Keywords / Materials (for Non-textual outputs)

MODELS

Access to Document

Storkey 2004 Generalised Propagation for Fast Fourier TransformsAccepted author manuscript, 145 KB

http://papers.nips.cc/paper/2505-generalised-propagation-for-fast-fourier-transforms-with-partial-or-missing-data

Cite this

Storkey, AJ. (2004). Generalised propagation for fast Fourier transforms with partial or missing data. In S. Thrun, K. Saul, & B. Scholkopf (Eds.), ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 16: Proceedings of the 2003 Conference (pp. 433-440). (ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS; Vol. 16). MIT Press. http://papers.nips.cc/paper/2505-generalised-propagation-for-fast-fourier-transforms-with-partial-or-missing-data

@inproceedings{54fb1cc0a8824a5d94b1abca3640706c,

title = "Generalised propagation for fast Fourier transforms with partial or missing data",

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 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.",

keywords = "MODELS",

author = "AJ Storkey",

year = "2004",

language = "English",

isbn = "0-262-20152-6",

series = "ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS",

publisher = "MIT Press",

pages = "433--440",

editor = "S Thrun and K Saul and B Scholkopf",

booktitle = "ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 16",

note = "17th Annual Conference on Neural Information Processing Systems (NIPS) ; Conference date: 08-12-2003",

}

Storkey, AJ 2004, Generalised propagation for fast Fourier transforms with partial or missing data. in S Thrun, K Saul & B Scholkopf (eds), ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 16: Proceedings of the 2003 Conference. ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS, vol. 16, MIT Press, CAMBRIDGE, pp. 433-440, 17th Annual Conference on Neural Information Processing Systems (NIPS), Canada, 8/12/03. <http://papers.nips.cc/paper/2505-generalised-propagation-for-fast-fourier-transforms-with-partial-or-missing-data>

Generalised propagation for fast Fourier transforms with partial or missing data. / Storkey, AJ.
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 16: Proceedings of the 2003 Conference. ed. / S Thrun; K Saul; B Scholkopf. CAMBRIDGE: MIT Press, 2004. p. 433-440 (ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS; Vol. 16).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Generalised propagation for fast Fourier transforms with partial or missing data

AU - Storkey, AJ

PY - 2004

Y1 - 2004

N2 - 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 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.

AB - 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 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.

KW - MODELS

M3 - Conference contribution

SN - 0-262-20152-6

T3 - ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS

SP - 433

EP - 440

BT - ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 16

A2 - Thrun, S

A2 - Saul, K

A2 - Scholkopf, B

PB - MIT Press

CY - CAMBRIDGE

T2 - 17th Annual Conference on Neural Information Processing Systems (NIPS)

Y2 - 8 December 2003

ER -

Generalised propagation for fast Fourier transforms with partial or missing data

Abstract

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this