Computing Fourier Transforms and Convolutions on the 2-Sphere

Abstract

This paper considers the problem of efficient computation of the spherical harmonic expansion, or Fourier transform, of functions defined on the two dimensional sphere, S2. The resulting algorithms are applied to the efficient computation of convolutions of functions on the sphere. We begin by proving convolution theorems generalizing well known and useful results from the abelian case. These convolution theorems are then used to develop a sampling theorem on the sphere. which reduces the calculation of Fourier transforms and convolutions of band-limited functions to discrete computations. We show how to perform these efficiently, starting with an O(n(log n)2) time algorithm for computing the Legendre transform of a function defined on the interval [−1,1] sampled at n points there. Theoretical and experimental results on the effects of finite precision arithmetic are presented. The Legendre transform algorithm is then generalized to obtain an algorithm for the Fourier transform, requiring O(n(log n)2) time, and an algorithm for its inverse in O(n1.5) time, where n is the number of points on the sphere at which the function is sampled. This improves the naive O(n2) bound, which is the best previously known. These transforms give an O(n1.5) algorithm for convolving two functions on the sphere.