The XFT Quadrature in Discrete Fourier Analysis

The Fourier transform is without any doubt an essential tool in applications such as signal and image processing. It is an integral transform that can be discretized in an algorithm called the Discrete Fourier Transform (DFT). Basically, that means replacing the integral by a numerical quadrature formula. A smart implementation turns this into a Fast Fourier Transform (FFT) procedure that has become a widely used numerical computational technique that is stable (because it is an orthogonal transform) and fast (the typical order is N log N for signals of size N). So it may be surprising that after decades of intensive use and analysis, something new is added.

The one-dimensional Fourier transform can be considered as a rotation over ninety degrees in an orthogonal time-frequency representation of the data. The original signal given as a function of time on a time axis is transformed into its spectral contents that is as a function of frequency and the frequency axis is orthogonal to the time axis. In optical systems, certain lens combinations can transform (rotate) the data over any angle, which is called a fractional Fourier transform (FrFT). The classical Fourier transforms is a special case of the FrFT, which in turn is a special case of an even more general linear fractional transforms (LFT). The latter kind of transforms has applications in quantum theory. The FrFT is like computing a fractional power of the ordinary Fourier transform. The extended Fourier transform (XFT) discussed in this book emerged by defining a discrete version of the Fourier transform in a slightly different way than what is done in the classical DFT. In the XFT, it is implemented as a special case of a discrete version of the FrFT. The result is a procedure that is as fast as the FFT, but slightly more accurate.

In the first introductory chapter, the ordinary DFT is recalled and it is illustrated that for non-periodic functions and when the N is not very large, some errors will occur as a consequence of the discretization. The DFT occurs as a unitary matrix that multiplies the data vector of the sampled signal to generate the frequency vector representation of the same signal. In this introduction also the two-dimensional transform is considered. It is illustrated that the effect of a translation in the transform, is a cyclic shift of the image, but it also has some other side effects.

The second chapter introduces the XFT, which requires a discussion of the Hermite functions. That are the eigenfunctions of the Fourier transform. It is shown how they feature in discretized versions of the transform, i.e., in the alternative quadrature approximation of the Fourier transform. This quadrature was introduced by the author and his co-workers in their paper A new formulation of the fast fractional Fourier transform SIAM J. Sci. Comp. 34(2) A1110–A1125 (2012). Instead of equidistant nodes, it uses the zeros of the Hermite function of order N. The (matrix representing the) XFT has its own eigenvectors, which can be seen as discretized versions of the Hermite functions. Since the Hermite functions are orthogonal, one wants to make sure that the eigenvectors are orthogonal as well. Also the even and odd properties of the Hermite functions are preserved in the discretized eigenvectors. This discrete XFT version has a differentiation matrix with interesting properties, which in fact allows to obtain also fractional powers of the differentiation operator. The core of the eventual XFT implementation is an ordinary FFT that is applied to a scaled and re-sampled data vector. The FFT result is then scaled back to the original setting. Classical issues like the discrete cosine transform, problems of sampling and aliasing, and two-dimensional versions are briefly discussed.

The next two chapters give a survey of many applications where the XFT can be used, mainly (partial) differential equations, and that includes usual derivatives as well as fractional derivatives (and integrals), and other fractional transforms (Laplace, Hilbert, derivative,...) and the generalization to fractional Fourier transforms and linear canonical transforms. The two appendices describe the mathematica and the matlab codes for the implementation of the XFT.

The book gives a concise survey of problems with classical DFT and introduces the XFT as an alternative. The performance is clearly illustrated with many applications and above all, the code to compute the XFT (and related algorithms) are provided both in mathematica and matlab, so that it is possible to immediately start experimenting with the methods. Recommended for everyone who uses Fourier transforms in a computational context and wants to learn about its extended XFT alternative and the theory behind it.

Adhemar Bultheel
Book details

The extended Fourier transform (XFT) is, like the discrete Fourier transform (DFT), an approximation of the continuous Fourier transform by a quadrature that approximates the integral of the transform. The XFT first published in 2012 by the author and his co-workers differs slightly from the DFT by an appropriate choice of the nodes of the quadrature. The result is a discrete transform that is as fast as the DFT, but that performs slightly better. The method is explained, several applications illustrate the method and the codes in mathematica and matlab are provided.

Author:  Publisher: 
978-3-030-13422-8 (hbk); 978-3-030-13423-5 (ebk)
€ 88.39 (hbk); € 51.16 (ebk)