Computing Fourier Transforms and Convolutions on the 2-Sphere

By James R. Driscoll, Dennis M. Healy Jr.. 1994

This paper considers the problem of efficient computation of the spherical harmonic expansion, or Fourier transform, of functions defined on the two dimensional sphere, S^2. 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(n^1^.^5) time, where n is the number of points on the sphere at which the function is sampled. This improves the naive O(n^2) bound, which is the best previously known. These transforms give an O(n^1^.^5) algorithm for convolving two functions on the sphere.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Clebsch-Gordan Nets: a Fully Fourier Space Spherical Convolutional Neural Network (2018, methodology): “This signal is then discretized using Driscol-Healy [32] grid using a bandwidth of b = 10.”
Spherical CNNs (2018, methodology): “This signal is discretized using a Driscoll-Healy grid (Driscoll and Healy, 1994) with bandwidth b = 128 .”
DeepSphere: a graph-based spherical CNN (2020, methodology): “In this work, depending on the considered application, we will use the equiangular (Driscoll & Healy, 1994), HEALPix (Gorski et al., 2005), and icosahedral (Baumgardner & Frederickson, 1985) samplings.”
e3nn: Euclidean Neural Networks (2022, methodology): “The grid we use is chosen to improve the performance of the transformation[9].”
3D object classification and retrieval with Spherical CNNs (2017, methodology): “We also implement a potentially faster method based on separation of variables, shown by [9].”
Stereographic wavelet frames on the sphere (2005, methodology): “Actually, {θp} constitutes a pseudo-spectral grid, localized on the zeros of a Chebishev polynomial of order 2β [8, 11].”
Protein–protein docking by fast generalized Fourier transforms on 5D rotational manifolds (2016, unknown): “4 looks like a Fourier transform but e − imφ is replaced by d lm ( cosθ ) e − imφ which shows the non-Cartesian properties of the sphere [17].”
SHREC 2007 3 D Shape Retrieval Contest (2006, background): “Eight groups initially registered, five groups actually participated [7, 8, 9, 10, 11].”
GemNet: Universal Directional Graph Neural Networks for Molecules (2021, unknown): “This can be expressed as [15] H̃dir a (X,H)(r̂o) = θHa(r̂o) + ∫”
Correspondence-free Structure from Motion (2007, methodology): “... samples in each spherical coordinate (see Fig. 5). Recalling Eq. (11), a spherical harmonic is a product of a Legendre polynomial (in the longitudinal parameter θ) with a complex exponential (in the azimuthal parameter φ). The SFT amounts to performing many Legendre transforms in θ followed by m”
A spectral solution of the magneto-convection equations in spherical geometry (2000, background): “A fast Legendre transform does exist [34], but only becomes competitive at truncations beyond what one can do in a fully three-dimensional calculation.”
Fully Automatic Registration of 3D Point Clouds (2006, methodology): “Fortunately, due in part to our selection of a uniform angular sampling of the sphere, there exists a separation-of-variables technique to compute the discrete SFT in O(L(2)log(2)L) [8].”
Deep Learning 3D Shapes Using Alt-az Anisotropic 2-Sphere Convolution (2018, background): “(2003); Frome et al. (2004); Makadia & Daniilidis (2010)), remeshing (Praun & Hoppe (2003)), medical imaging (Shen & Makedon (2006)) and other tasks before the deep learning era.”
Constraints on the Martian lithosphere from gravity and topography data and implication for volcanism and possible mantle heterogeneities (2005, methodology): “With such a grid, the spherical harmonics transform used to compute the horizontal derivatives and gradients is easily performed [see Lognonné and Romanowicz , 1990; Driscoll and Healy , 1994; Sneeuw , 1994].”