Fast Fourier Analysis on Groups

This webpage intends to collect together some people, papers and software related to group theoretic approaches to Fourier analysis.
Send questions and comments to Dan Rockmore rockmore@cs.dartmouth.edu or Peter Kostelec geelong@cs.dartmouth.edu

Shortcuts:

Brief Background

 The Fast Fourier Transform (FFT) is one of the most important family of algorithms in applied and computational mathematics. These are the algorithms that make most of signal processing, and hence modern telecommunications possible. The most basic divide and conquer approach was originally discovered by Gauss for the efficient interpolation of asteroidal orbits. Since then, various versions of the algorithm have been discovered and rediscovered many times, culminating with the publishing of Cooley and Tukey's landmark paper, "An algorithm for machine calculation of complex Fourier series", Math. Comp. 19 (1965), 297--301. Nice historical surveys are

J. W. Cooley, "The re-discovery of the fast Fourier transform algorithm", Mikrochimica Acta III (1987), 33--45.

J. W. Cooley, "How the FFT gained acceptance", Proceedings of the ACM conference on the history of scientific and numeric computation, Princeton, NJ May 13--15, 1987, 133--140.

M. T. Heideman, D. H. Johnson, and C. S. Burrus, Gauss and the history of the fast Fourier transform, Archive for History of Exact Sciences 34(3) (1985), 265--277.

There are many ways to approach the FFT. The point of view of the work collected here is a group theoretic one. In this setting the FFT is a family of algorithms for the efficient expansion of a function defined on a finite or compact group in terms of a set of irreducible matrix coefficients for the group. For the circle these are precisely the exponentials or sampled exponentials in the case of the discrete circle. Consideration of noncommutative groups gives rise to the many families of special functions, the most familiar of which are probably the Legendre functions and other Gegenbauer polynomials and systems of orthogonal polynomials.

We assume that initially, the function is "given" as a finite set of sample values on the group in question - in the classical setting the group is the circle (discrete or continuous) and is usually identified with time or space - and the forward Fourier transform consists in the computation of the Fourier coefficients for the expansion of the function in terms of a predetermined set of irreducible matrix coefficients on the group. Of course the assumption is that these are finite expansions, and this effectively defines the general notion of "bandlimited" as a function with finite expansion in terms of irreducible matrix coefficients.

For a more thorough introduction to these ideas see the survey papers

  • D. Maslen and D. Rockmore, "Generalized FFTs -- A survey of some recent results" Proc. 1995 DIMACS Workshop in Groups and Computation, L. Finkelstein and W. Kantor (eds.), Dimacs Series in Disc. Math. and Comp. Sci, Volume 28, pp. 183--238. and
  • D. Rockmore, "Some applications of generalized FFTs" Proc. 1995 DIMACS Workshop in Groups and Computation, L. Finkelstein and W. Kantor (eds.), Dimacs Series in Disc. Math. and Comp. Sci, Volume 28, pp. 329--370.

    People

    Motivated by a variety of applications to data analysis and combinatorics a loosely knit group of us have been working on different aspects of the development and application of these algorithms. Here are some of us:

    For related work also see

    Wavelet Warriors homepage

    Current projects

    At present (June 1999) our work mainly falls into two categories:

    FFTs for the 2-sphere

     An FFT for the 2-sphere is defined to be an efficient algorithm for the expansion of a bandlimited function on the 2-sphere in terms of spherical harmomics. This falls into our framework by considering such functions as right SO(2)-invariant functions on the group SO(3). A function on the 2-sphere has bandwidth B if its expansion requires only spherical harmonics of order at most B. This implies at most B^2 Fourier coefficients, which if computed directly (using an appropriate sampling theorem) requires on the order of (B^2)^2 = B^4 operations. In 1989 Driscoll and Healy discovered a B^2\log^2(B^2) algorithm by using the three-term recurrence satisfied by the Legendre functions (J. R. Driscoll and D. Healy, "Computing Fourier transforms and convolutions on the 2-sphere", Proc. 34th IEEE FOCS, (1989) 344--349 (extended abstract); Adv. in Appl. Math., 15 (1994), 202--250). A later reformulation of the algorithm gives a reduction of the inverse transform to an algorithm of the same order of complexity (D. Healy, P. Kostelec, S. Moore, and D. Rockmore, "Efficiency and reliability issues in a fast Fourier transform on the 2-sphere", Technical Report, Department of Computer Science, Dartmouth College, 1994). We are currently working to obtain effective implementations of these ideas. A preprint describing algorithms for computing Fourier transforms of tensor fields on the 2-sphere can be found here.

    FFTs for finite groups

     An FFT for a finite group is an efficient algorithm for computing the expansion of a function in terms of irreducible matrix coefficients. Direct computation of such an expansion (from the input of sample values) would require |G|^2 operations. It is conjectured that there is an O( |G| log^c |G|) upper bound for all groups G. To date, this is known to be true for commutative groups, symmetric groups and their wreath products, as well as supersolvable groups. The "separation of variables" approach unifies most of the fast algorithms within a general framework. For applications, we are particularly interested in implementations of FFTs for symmetric groups (useful for the analysis of ranked data), wreath products (useful for analysis of data from experimental designs and image processing) and SL_2(F), for F a finite field (useful for coding theory ).

    Software

    There have been visitors since March 20, 1998. This work has been partially funded by an NSF Presidential Faculty Fellowship, NSF DMS-9553134.