Asymptotically fast algorithms for spherical and related transforms
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 344-349
- https://doi.org/10.1109/sfcs.1989.63501
Abstract
The problem of computing the convolution of two functions on the sphere by means of a spherical transform is considered. Such convolutions are applicable to surface recognition and the location of both rotated and translated patterns in an image. The authors give convolution theorems that relate the spherical transform to convolution, sampling theorems that allow the exact computation of the transform for band-limited functions, and algorithms with asymptotically improved running time for the exact computation of the harmonic expansion. The net result is an O(n/sup 1.5/(log n)/sup 2/) algorithm for the exact computation of the convolution of two bandlimited functions sampled at n points in accordance with the sampling theorem. The techniques developed are applicable to computing other transforms, such as the Laguerre, Hermite, and Hankel transforms.Keywords
This publication has 4 references indexed in Scilit:
- Computation of spherical harmonic expansion coefficients via FFT'sJournal of Computational Physics, 1985
- Harmonic Analysis on Symmetric Spaces and Applications IPublished by Springer Nature ,1985
- Special Functions and the Theory of Group RepresentationsPublished by American Mathematical Society (AMS) ,1968
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965