FFTs on the Rotation Group

Earlier work by Driscoll and Healy [4] has produced an efficient O(B2 log2 B) algorithm for computing the Fourier transform of band-limited functions on the 2-sphere. In this paper, we discuss an implementation of an O(B4) algorithm for the numerical computation of Fourier transforms of functions defined on the rotation group, SO(3). This compares with the direct O(B6) approach. The algorithm we implemented is based on the “Separation of Variables” technique, e.g. as presented by Maslen and Rockmore [18]. In conjunction with the techniques developed in [4], the SO(3) algorithm we implemented may be made truly fast, O(B3 log2 B). Basic results will be presented establishing the algorithm's numerical stability, and applications will be discussed.