A fast algorithm for nonequispaced Fourier transforms on the rotation group

Daniel Potts; Jürgen Prestin; Antje Vollrath

doi:10.1007/s11075-009-9277-0

A fast algorithm for nonequispaced Fourier transforms on the rotation group

Daniel Potts^*, Jürgen Prestin, Antje Vollrath

^*Corresponding author for this work

Institute of Mathematics

Graduate School for Computing in Medicine and Life Sciences

37 Citations (Scopus)

Abstract

In this paper we present algorithms to calculate the fast Fourier synthesis and its adjoint on the rotation group SO(3) for arbitrary sampling sets. They are based on the fast Fourier transform for nonequispaced nodes on the three-dimensional torus. Our algorithms evaluate the SO(3) Fourier synthesis and its adjoint, respectively, of B-bandlimited functions at M arbitrary input nodes in O(M+B⁴) or even O(M + B³ log² B) flops instead of O(MB³). Numerical results will be presented establishing the algorithm's numerical stability and time requirements.

Original language	English
Journal	Numerical Algorithms
Volume	52
Issue number	3
Pages (from-to)	355-384
Number of pages	30
ISSN	1017-1398
DOIs	https://doi.org/10.1007/s11075-009-9277-0
Publication status	Published - 01.10.2009

Funding

Acknowledgements D. Potts gratefully acknowledges financial support by Deutsche Forschungsgemeinschaft, grant PO 711/9-1 and A. Vollrath gratefully acknowledges financial support by the Lübeck Graduate School for Computing in Medicine and Life Sciences. Moreover, we like to thank the referees for their valuable suggestions.

Access to Document

10.1007/s11075-009-9277-0

Cite this

@article{6e6c14ef48384d72b842e493edaba9ae,

title = "A fast algorithm for nonequispaced Fourier transforms on the rotation group",

abstract = "In this paper we present algorithms to calculate the fast Fourier synthesis and its adjoint on the rotation group SO(3) for arbitrary sampling sets. They are based on the fast Fourier transform for nonequispaced nodes on the three-dimensional torus. Our algorithms evaluate the SO(3) Fourier synthesis and its adjoint, respectively, of B-bandlimited functions at M arbitrary input nodes in O(M+B4) or even O(M + B3 log2 B) flops instead of O(MB3). Numerical results will be presented establishing the algorithm's numerical stability and time requirements.",

author = "Daniel Potts and J{\"u}rgen Prestin and Antje Vollrath",

year = "2009",

month = oct,

day = "1",

doi = "10.1007/s11075-009-9277-0",

language = "English",

volume = "52",

pages = "355--384",

journal = "Numerical Algorithms",

issn = "1017-1398",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - A fast algorithm for nonequispaced Fourier transforms on the rotation group

AU - Potts, Daniel

AU - Prestin, Jürgen

AU - Vollrath, Antje

PY - 2009/10/1

Y1 - 2009/10/1

N2 - In this paper we present algorithms to calculate the fast Fourier synthesis and its adjoint on the rotation group SO(3) for arbitrary sampling sets. They are based on the fast Fourier transform for nonequispaced nodes on the three-dimensional torus. Our algorithms evaluate the SO(3) Fourier synthesis and its adjoint, respectively, of B-bandlimited functions at M arbitrary input nodes in O(M+B4) or even O(M + B3 log2 B) flops instead of O(MB3). Numerical results will be presented establishing the algorithm's numerical stability and time requirements.

AB - In this paper we present algorithms to calculate the fast Fourier synthesis and its adjoint on the rotation group SO(3) for arbitrary sampling sets. They are based on the fast Fourier transform for nonequispaced nodes on the three-dimensional torus. Our algorithms evaluate the SO(3) Fourier synthesis and its adjoint, respectively, of B-bandlimited functions at M arbitrary input nodes in O(M+B4) or even O(M + B3 log2 B) flops instead of O(MB3). Numerical results will be presented establishing the algorithm's numerical stability and time requirements.

UR - https://www.scopus.com/pages/publications/70350400724

U2 - 10.1007/s11075-009-9277-0

DO - 10.1007/s11075-009-9277-0

M3 - Journal articles

AN - SCOPUS:70350400724

SN - 1017-1398

VL - 52

SP - 355

EP - 384

JO - Numerical Algorithms

JF - Numerical Algorithms

IS - 3

ER -

A fast algorithm for nonequispaced Fourier transforms on the rotation group

Abstract

Funding

Access to Document

Other files and links

Fingerprint

Graduate School GSC 235: Graduate School for Computing in Medicine and Life Sciences

Cite this

A fast algorithm for nonequispaced Fourier transforms on the rotation group

Abstract

Funding

Access to Document

Other files and links

Fingerprint

Projects

Graduate School GSC 235: Graduate School for Computing in Medicine and Life Sciences

Cite this