Fast Summation of Functions on the Rotation Group

Computing with functions on the rotation group is a task carried out in various areas of application. When it comes to approximation, kernel based methods are a suitable tool to handle these functions. In this paper, we present an algorithm which allows us to evaluate linear combinations of functions on the rotation group as well as a truly fast algorithm to sum up radial functions on the rotation group. These approaches based on nonequispaced FFTs on SO(3) take O(M+N)\mathcal{O}(M+N) arithmetic operations for M and N arbitrarily distributed source and target nodes, respectively. In this paper, we investigate a selection of radial functions and give explicit theoretical error bounds, as well as numerical examples of approximation errors. Moreover, we provide an application of our method, namely the kernel density estimation from electron back scattering diffraction (EBSD) data, a problem relevant in texture analysis.