Nonequispaced fast Fourier transform
NFFT on SO(3)

# NFSOFT - NFFT on the rotation group

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

This library of C functions evaluates a function $$f \in \mathrm{L}^2(SO(3))$$ with finite orthogonal expansion $f(\alpha,\beta,\gamma)=\sum_{l=0}^{B}\sum_{m=-l}^l\sum_{n=-l}^{l}\widehat f^{m,n}_lD^{m,n}_l(\alpha,\beta,\gamma).$ in terms of Wigner-D functions $$D^{m,n}_l$$ on a set of arbitary nodes $$\left(\alpha_d,\beta_d,\gamma_d\right)$$, $$d=1,\ldots,D$$, $$D \in \mathbb{N}$$, in Euler angles. Furthermore, the fast evaluation of sums $\tilde{\widehat f}^{m,n}_l:= \sum_{d=1}^{D} f\left(\alpha_d,\beta_d,\gamma_d\right) \overline{ D^{m,n}_l \left(\alpha_d,\beta_d,\gamma_d\right)}$ for given function values $$f\left(\alpha_d,\beta_d,\gamma_d\right) \in \mathbb{C}$$ and all indices $$l,m,n$$ is the adjoint NFSOFT.

The algorithms are implemented by Antje Vollrath in ./kernel/nfsoft. The OpenMP parallelization and the Matlab interface in ./matlab/nfsoft are implemented by Michael Quellmalz. Related papers are

• Gräf, M., Potts, D.
Sampling sets and quadrature formulae on the rotation group.
Numer. Funct. Anal. Optim. 30, 665 - 688,   (full paper ps, pdf),   2009

• Potts, D., Prestin J., Vollrath A.
A Fast algorithm for nonequispaced Fourier transforms on the rotation group.
Numer. Algorithms, 52, 355 - 384,   (full paper ps, pdf),   2009

• Hielscher, R., Potts, D., Prestin, J., Schaeben, H., Schmalz, M.
The Radon transform on SO(3): A Fourier slice theorem and numerical inversion.
Inverse Problems 24, 025011,   (full paper ps, pdf),   2008