A fast algorithm for nonequispaced Fourier transforms on the rotation group (Q1039276)

In this interesting paper, the authors present novel algorithms to calculate the fast Fourier synthesis and its adjoint transform on the rotation group \(SO(3)\) for arbitrary sampling sets. The algorithm to compute an \(SO(3)\) Fourier synthesis is based on evaluating the Wigner-D functions \(D_l^{mn}\), which yield an orthogonal basis of \(L^2(SO(3))\). The authors present a method for the efficient and accurate calculation of the \(SO(3)\) Fourier synthesis \[ f(g_q)=\sum_{l=0}^B \sum_{m,n=-l}^l {\hat f}_l^{mn}\, D_l^{mn}(g_q) \] of a \(B\)-bandlimited function \(f\in L^2(SO(3))\) at \(M\) arbitrary samples \(g_q\in SO(3)\) \((q=0,\ldots,M-1)\). These algorithms are mainly based on the fast Fourier transform for nonequispaced nodes on the 3-dimensional torus. Thus the \(SO(3)\) Fourier synthesis requires \({\mathcal O}(M + B^3\, \log^2 B)\) flops instead of \({\mathcal O}(M\,B^3)\), where a typical size of \(M\) is \({\mathcal O}(B^3)\). Numerical tests show the high performance of this method.