Copyrights to these papers may be held by the publishers. The download files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Doru Balcan, Aliaksei Sandryhaila, Jonathan Gross and Markus Püschel (Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 3537-3540, 2008)
Alternatives to the Discrete Fourier Transform
Preprint (601 KB)
Published paper (link to publisher)
Bibtex

It is well-known that the discrete Fourier transform (DFT) of a finite length discrete-time signal samples the discrete-time Fourier transform of the same signal at equidistant points on the unit circle. Hence, as the signal length goes to infinity, the DFT approaches the DTFT. Associated with the DFT are circular convolution and a periodic signal extension. In this paper we identify a large class of alternatives to the DFT using the theory of polynomial algebras. Each of these Fourier transforms approaches the DTFT just as the DFT does, but has its own signal extension and notion of convolution. Further, these Fourier transforms have Vandermonde structure, which enables their fast computation. We provide a few experimental examples that confirm our theoretical results.

Keywords:
Algebraic signal processing theory: Current status, Discrete Fourier transform