×

On the diagonalization of the discrete Fourier transform. (English) Zbl 1165.65089

The authors describe a representation theoretic approach to the diagonalization problem of the discrete Fourier transform of length \(p\), where \(p>2\) is a prime number. Starting with the Weil representation of the finite symplectic group, the theory of tori in the one-dimensional Weil representation is discussed. Using a relation between the DFT and the Weil representation, a canonical basis \(\Phi\) of eigenvectors for the DFT is presented. The transition matrix \(\Theta\) from the standard basis to \(\Phi\) defines a novel transform, the so-called discrete oscillator transform. Finally, a fast algorithm for computing \(\Theta\) in certain cases is described.

MSC:

65T50 Numerical methods for discrete and fast Fourier transforms
43A65 Representations of groups, semigroups, etc. (aspects of abstract harmonic analysis)
11F27 Theta series; Weil representation; theta correspondences
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Auslander, L.; Tolimieri, R., Is computing with the finite Fourier transform pure or applied mathematics?, Bull. Amer. Math. Soc. (N.S.), 1, 6, 847-897 (1979) · Zbl 0475.42014
[2] Beyl, F. R., The Schur multiplicator of \(SL(2, Z / m Z)\) and the congruence subgroup property, Math. Z., 191 (1986) · Zbl 0581.20050
[3] Coxeter, H. S.M.; Moser, W. O.J., Generators and Relations for Discrete Groups, Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 14 (1980), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0422.20001
[4] Cooley, J. W.; Tukey, J. W., An algorithm for the machine calculation of complex Fourier series, Math. Comput., 19, 297-301 (1965) · Zbl 0127.09002
[5] Dickinson, B. W.; Steiglitz, K., Eigenvectors and functions of the discrete Fourier transform, IEEE Tans. Acoust. Speech Signal Process., 30, 1, 25-31 (1982) · Zbl 0563.65022
[6] Feichtinger, H. G.; Hazewinkel, M.; Kaiblinger, N.; Matusiak, E.; Neuhauser, M., Metaplectic operators on \(C^n\), Q. J. Math., 59, 1, 15-28 (2008) · Zbl 1142.22007
[7] Fulton, W.; Harris, J., Representation theory. A first course, (Readings in Mathematics. Readings in Mathematics, Graduate Texts in Mathematics, vol. 129 (1991), Springer-Verlag: Springer-Verlag New York) · Zbl 0744.22001
[8] Grünbaum, F. A., The eigenvectors of the discrete Fourier transform, J. Math. Anal. Appl., 88, 355-363 (1982) · Zbl 0516.65099
[9] S. Gurevich, R. Hadani, The Geometric Weil Representation, Selecta Mathematica, New Series, Birkhäuser, Basel, 2006, in press; S. Gurevich, R. Hadani, The Geometric Weil Representation, Selecta Mathematica, New Series, Birkhäuser, Basel, 2006, in press · Zbl 1163.22004
[10] Gurevich, S.; Hadani, R., Quantization of symplectic vector spaces over finite fields (2005), preprint
[11] S. Gurevich, R. Hadani, R. Howe, Quadratic reciprocity and sign of Gauss sum via the finite Weil representation (2008), submitted for publication; S. Gurevich, R. Hadani, R. Howe, Quadratic reciprocity and sign of Gauss sum via the finite Weil representation (2008), submitted for publication · Zbl 1231.11093
[12] Gurevich, S.; Hadani, R.; Sochen, N., The finite harmonic oscillator and its associated sequences, Proc. Natl. Acad. Sci. USA, 105, 29, 9869-9873 (2008) · Zbl 1205.94034
[13] S. Gurevich, R. Hadani, N. Sochen, On some deterministic dictionaries supporting sparsity, in: A. Cohen, R. DeVore, M. Elad, A. Gilbert (Eds.), J. Fourier Anal. Appl. (2008), in press; S. Gurevich, R. Hadani, N. Sochen, On some deterministic dictionaries supporting sparsity, in: A. Cohen, R. DeVore, M. Elad, A. Gilbert (Eds.), J. Fourier Anal. Appl. (2008), in press · Zbl 1183.94010
[14] S. Gurevich, R. Hadani, N. Sochen, The finite harmonic oscillator and its application to sequences, communication and radar, IEEE Trans. Inform. Theory (2008), in press; S. Gurevich, R. Hadani, N. Sochen, The finite harmonic oscillator and its application to sequences, communication and radar, IEEE Trans. Inform. Theory (2008), in press · Zbl 1322.94031
[15] Hasse, H.; Davenport, H., Die Nullstelen der Kongruenzzetafunktionen in gewissen zyklischen Fallen, J. Reine Angew. Math., 172, 151-182 (1934) · JFM 60.0913.01
[16] Mehta, M. L., Eigenvalues and eigenvectors of the finite Fourier transform, J. Math. Phys., 28, 4, 781-785 (1987) · Zbl 0621.15019
[17] Vourdas, A., Quantum systems with finite Hilbert space: Galois fields in quantum mechanics, J. Phys. A, 40, 33, R285-R331 (2007) · Zbl 1176.81055
[18] Weil, A., Sur certains groupes d’operateurs unitaires, Acta Math., 111, 143-211 (1964) · Zbl 0203.03305
[19] Weyl, H., Gruppentheorie und Quantenmechanik (1928), Hirzel: Hirzel Leipzig · JFM 54.0954.03
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.