Some applications of generalized FFT's
Some applications of generalized FFT's
复制标题
广义FFT的一些应用
DOI：
10.1090/dimacs/028/19
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
D. Rockmore
中科院分区：
文献类型：
--
作者：
D. Rockmore
广义傅里叶变换是计算有限群上的函数或紧群上的带限函数的傅里叶变换的一种有效算法。这种算法的发展一直伴随着越来越多的潜在的和实现的应用程序和动机。本文将尝试调查其中的一些应用。附录包括一些更详细的例子。1.快速傅立叶变换（FFT）是一种经典的快速傅立叶变换，有着悠久而有趣的历史。它最初由高斯发现，后来被库利和图基重新发现后变得著名[21]，它可以被视为一种算法，它可以精确地计算离散傅里叶变换或DFT。在高斯和库利-图基之间，其他人开发了算法的特殊情况，通常是出于对一种或另一种数据进行分析的需要。仅举几个例子，高斯对小行星轨道的精确内插感兴趣[43];丹尼尔森和兰佐斯关注X射线衍射[23];耶茨[103]和古德[47]需要统计算法;库利和图基对精确的时间序列分析和数字信号处理[21]。对于彻底的历史概述见19，20，50]。最近，已经开发了与从群表示理论的观点来概括FFT的算法的构造相关的越来越多的文献（参见例如，5、17、18、29、82]）。这些类型的概括作为数学构造是“自然的”，但事实上，它们也是由应用所激发的。例如，看起来最早的非交换FFT的构造（由于Willsky）是为了寻找新的有效滤波器。后来的建筑已经被诸如ecient数据分析（cf. 26])和电路设计（cf. 6]），仅举几个例子。本文的目的是调查一些广义FFT的应用，从而（希望！）推动朝这个方向进一步努力。12丹尼尔·N. ROCKMORE FFT的一个早期版本是由于统计学家耶茨。他对析因设计数据的有效分析很感兴趣。第2节回顾了该算法，然后详细解释了它的推广形式的nite群或其商上的数据的谱分析的ecient计算。这是说明了一个较成功的应用程序之一，到目前为止的简短讨论.
Generalized FFTs are eecient algorithms for computing a Fourier transform of a function deened on nite group, or a bandlimited function de-ned on a compact group. The development of such algorithms has been accompanied and motivated by a growing number of both potential and realized applications. This paper will attempt to survey some of these applications. Appendices include some more detailed examples. 1. A brief history The now \classical" Fast Fourier Transform (FFT) has a long and interesting history. Originally discovered by Gauss, and later made famous after being rediscovered by Cooley and Tukey 21], it may be viewed as an algorithm which eeciently computes the discrete Fourier transform or DFT. In between Gauss and Cooley-Tukey others developed special cases of the algorithm, usually motivated by the need to make eecient data analysis of one sort or another. To cite but a few examples, Gauss was interested in eeciently interpolating the orbits of asteroids 43]; Danielson and Lanczos were concerned with x-ray diiraction 23]; Yates 103] and Good 47] needed the algorithm for statistics; Cooley and Tukey were interested in eecient time series analysis and digital signal processing 21]. For thorough historical overviews see 19, 20, 50]. Recently, there has developed a growing literature related to the construction of algorithms which generalize the FFT from the point of view of the theory of group representations (see e.g., 5, 17, 18, 29, 82]). These sorts of generalizations are \natural" as mathematical constructs, but in point of fact, they too have been motivated by applications. For example, the seemingly earliest construction of \nonabelian" FFTs (due to Willsky) was motivated by the search for new eecient lters 102]. Later constructions have been motivated by applications such as eecient data analysis (cf. 26]) and circuit design (cf. 6]), just to name a few examples. The purpose of this paper is to survey some of the applications of generalized FFTs and thereby (hopefully!) motivate further work in this direction. 1 2 DANIEL N. ROCKMORE One early version of the FFT is due to the statistician Yates. He was interested in the eecient analysis of data from factorial designs. Section 2 reviews this algorithm and then explains in some detail its generalization in the form of eecient computation of spectral analysis for data on a nite group or its quotient. This is illustrated by a brief discussion of one of the more successful applications to date …