Skip to main content
SpringerLink
Log in

FFTs on the Rotation Group

  • Published:
Journal of Fourier Analysis and Applications Aims and scope Submit manuscript

Abstract

We discuss an implementation of an efficient algorithm for the numerical computation of Fourier transforms of bandlimited functions defined on the rotation group SO(3). The implementation is freely available on the web. The algorithm described herein uses O(B 4) operations to compute the Fourier coefficients of a function whose Fourier expansion uses only (the O(B 3)) spherical harmonics of degree at most B. This compares very favorably with the direct O(B 6) algorithm derived from a basic quadrature rule on O(B 3) sample points. The efficient Fourier transform also makes possible the efficient calculation of convolution over SO(3) which has been used as the analytic engine for some new approaches to searching 3D databases (Funkhouser et al., ACM Trans. Graph. 83–105, [2003]; Kazhdan et al., Eurographics Symposium in Geometry Processing, pp. 167–175, [2003]). Our implementation is based on the “Separation of Variables” technique (see, e.g., Maslen and Rockmore, Proceedings of the DIMACS Workshop on Groups and Computation, pp. 183–237, [1997]). In conjunction with techniques developed for the efficient computation of orthogonal polynomial expansions (Driscoll et al., SIAM J. Comput. 26(4):1066–1099, [1997]), our fast SO(3) algorithm can be improved to give an algorithm of complexity O(B 3log 2 B), but at a cost in numerical reliability. Numerical and empirical results are presented establishing the empirical stability of the basic algorithm. Examples of applications are presented as well.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Biedenharn, L.C., Louck, J.D.: Angular Momentum in Quantum Mechanics. Addison-Wesley, Reading (1981)

    Google Scholar 

  2. Chirikjian, G.S., Kyatkin, A.B.: Engineering Applications of Noncommutative Harmonic Analysis: With Emphasis on the Rotation and Motion Groups. CRC Press, Boca Raton (2001)

    MATH  Google Scholar 

  3. Courant, R., Hilbert, D.: Methods of Mathematical Physics. Interscience Publishers, New York (1953)

    Google Scholar 

  4. Crowther, R.A.: The fast rotation function. In: Rossman, M.G. (ed.) The Molecular Replacement Method, pp. 173–178. Gordon and Breach, New York (1972)

    Google Scholar 

  5. Dilts, G.A.: Computation of spherical harmonic expansion coefficients via FFTs. J. Comput. Phys. 57(3), 439–453 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  6. Driscoll, J.R., Healy, D.: Computing Fourier transforms and convolutions on the 2-sphere (extended abstract). In: Proc. 34th IEEE FOCS (1989), pp. 344–349. Adv. in Appl. Math., vol. 15, pp. 202–250 (1994)

  7. Driscoll, J.R., Healy, D., Rockmore, D.: Fast discrete polynomial transforms with applications to data analysis for distance transitive graphs. SIAM J. Comput. 26(4), 1066–1099 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  8. Edmonds, A.R.: Angular Momentum in Quantum Mechanics. Princeton University Press, Princeton (1957)

    MATH  Google Scholar 

  9. Data Announcement 88-MGG-02: Digital relief of the Surface of the Earth. NOAA, National Geophysical Data Center, Boulder, Colorado (1988)

  10. FFTW is a free collection of fast C routines for computing the Discrete Fourier Transform in one or more dimensions. It includes complex, real, symmetric, and parallel transforms, and can handle arbitrary array sizes efficiently; FFTW is available at www.fftw.org

  11. Funkhouser, T., Min, P., Kazhdan, M., Chen, J., Halderman, A., Dobkin, D., Jacobs, D.: A search engine for 3D models. ACM Trans. Graph. 83–105 (2003)

  12. Garcia, J., Valles, J.J., Ferreira, C.: Detection of three-dimensional objects under arbitrary rotations based on range images. Optic Express 11(25), 3352 (2003)

    Article  Google Scholar 

  13. Gentleman, W.M., Sande, G.: Fast Fourier Transforms—for fun and profit. Proc. 1966 Fall Joint Computer Conference AFIPS 29, 563–578

  14. Hansen, J.E.: Spherical Near-Field Antenna Measurements. Peter Peregrinus, London (1988)

    Google Scholar 

  15. Healy, D., Kim, P.: An empirical Bayes approach to directional data and efficient computation on the sphere. Ann. Stat. 24(1), 232–254 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  16. Healy, D., Hendriks, H., Kim, P.: Spherical deconvolution with application to geometric quality assurance. Technical Report, Department of Mathematics and Computer Science, Dartmouth College (1993)

  17. Healy, D.M., Kostelec, P., Rockmore, D.: Towards safe and effective high-order Legendre transforms with applications to FFTs for the 2-sphere. Adv. Comput. Math. 21(1–2), 59–105 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  18. Healy, D., Rockmore, D., Kostelec, P., Moore, S.: FFTs for the 2-Sphere—Improvements and Variations. J. Fourier Anal. Appl. 9(4), 341–385 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  19. Kazhdan, M., Funkhouser, T., Rusinkiewicz, S.: Rotation invariant spherical harmonic representation of 3D shape descriptors. In: Kobbelt, L., Schröder, P., Hoppe, H. (eds.) Eurographics Symposium in Geometry Processing, pp. 167–175 (2003)

  20. Kostelec, P.J., Maslen, D.K., Healy, D.M., Rockmore, D.N.: Computational harmonic analysis for tensor fields on the two-sphere. J. Comput. Phys. 162, 514–535 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  21. Kovacs, J.A., Wriggers, W.: Fast rotational matching. Acta Crystallogr. D Biol. Crystallogr. 58(8), 1282–1286 (2002)

    Article  Google Scholar 

  22. Maslen, D.: Efficient computation of Fourier transform on compact groups. J. Fourier Anal. Appl. 4(1), 19–52 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  23. Maslen, D., Rockmore, D., Generalized FFTs. In: Finkelstein, L., Kantor, W. (eds.) Proceedings of the DIMACS Workshop on Groups and Computation, June 7–10, 1995, pp. 183–237 (1997)

  24. Maslen, D., Rockmore, D.: Separation of variables and the computation of Fourier transforms on finite groups, I. J. Am. Math. Soc. 10(1), 169–214 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  25. The National Geophysical Data Center (NGDC), located in Boulder, Colorado, is a part of the US Department of Commerce (USDOC), National Oceanic & Atmospheric Administration (NOAA), National Environmental Satellite, Data and Information Service (NESDIS). They are one of three NOAA National Data Centers, www.ngdc.noaa.gov

  26. Nikiforov, A.F., Suslov, S.K., Uvarov, V.B.: Classical Orthogonal Polynomials of a Discrete Variable, Springer Series in Computational Physics. Springer, Berlin (1991)

    Google Scholar 

  27. Oppenheim, A.V., Schafer, R.: Digital Signal Processing. Prentice-Hall, Englewood Cliffs (1975)

    MATH  Google Scholar 

  28. Risbo, T.: Fourier transform summation of Legendre series and D-functions. J. Geod. 70, 383–396 (1996)

    MATH  Google Scholar 

  29. Rokhlin, V., Tygert, M.: Fast algorithms for spherical harmonic expansions. SIAM J. Comput. 27(6), 1903–1928 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  30. The Princeton Shape Retrieval and Analysis Group, www.cs.princeton.edu/gfx/proj/shape/, whose goal is to “… investigate issues in shape-based retrieval and analysis of 3D models,” has developed a 3D search engine as part of their work, shape.cs.princeton.edu

  31. SpharmonicKit is a freely available collection of C programs for doing Legendre and scalar spherical transforms. Developed at Dartmouth College by S. Moore, D. Healy, D. Rockmore, and P. Kostelec, available at www.cs.dartmouth.edu/~geelong/sphere/

  32. The SOFT Package is a freely available collection of C programs for doing Wigner-d transforms, as well as forward and inverse Fourier transforms of functions defined on the Rotation Group, SO(3). The package also includes example routines for correlating functions defined on S 2, The package is available at www.cs.dartmouth.edu/~geelong/soft/

  33. Varshalovich, D.A., Moskalev, A.N., Khersonskii, V.K.: Quantum Theory of Angular Momentum. World Scientific Publishing, Singapore (1988)

    Google Scholar 

  34. Vilenkin, N.J.: Special Functions and the Theory of Group Representations, Translations of Mathematical Monographs, vol. 22. Am. Math. Soc., Providence (1968)

    MATH  Google Scholar 

  35. Wandelt, B.D., Górski, K.M.: Fast convolution on the sphere. Phys. Rev. D 63, 123002 (2001)

    MathSciNet  Google Scholar 

  36. Wigner, E.P.: On matrices which reduce Kronecker products of representations of S.R. groups, unpublished (1951)

  37. Wigner, E.P.: Group Theory and its Application to the Quantum Mechanics of Atomic Spectra. Academic Press, New York (1959)

    MATH  Google Scholar 

  38. Zelobenko, D.P.: Compact Lie groups and their representations, Transl. Math. Monogr., vol. 40. Am. Math. Soc., Providence (1973)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. MIT Lincoln Laboratory, 244 Wood Street, Lexington, MA, 02420, USA

    Peter J. Kostelec

  2. Department of Mathematics, Dartmouth College, Hanover, NH, 03755, USA

    Daniel N. Rockmore

Authors
  1. Peter J. Kostelec
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniel N. Rockmore
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniel N. Rockmore.

Additional information

Communicated by Thomas Strohmer.

First author was supported by NSF ITR award; second author was supported by NSF Grant 0219717 and the Santa Fe Institute.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kostelec, P.J., Rockmore, D.N. FFTs on the Rotation Group. J Fourier Anal Appl 14, 145–179 (2008). https://doi.org/10.1007/s00041-008-9013-5

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00041-008-9013-5

Keywords

Mathematics Subject Classification (2000)

Search

Navigation