Description

Fourier analysis has grown to become an essential mathematical tool with numerous applications in applied mathematics, engineering, physics, and other sciences. Many recent technological innovations from spectroscopy and computer tomography to speech and music signal processing are based on Fourier analysis. Fast Fourier algorithms are the heart of data processing methods, and their societal impact can hardly be overestimated.

The field of Fourier analysis is continuously developing toward the needs in applications, and many topics are part of ongoing intensive research. Due to the importance of Fourier techniques, there are several books on the market focusing on different aspects of Fourier theory.

Examining the existing textbooks in Fourier analysis, it appears as a shortcoming that the focus is either set only on the mathematical theory or vice versa only on the corresponding discrete Fourier and convolution algorithms, while the reader needs to consult additional references on the numerical techniques in the one case or on the analytical background in the other.

The urgent need for a unified presentation of Fourier theory and corresponding algorithms particularly emerges from new developments in function approximation using Fourier methods. It is important to understand how well a continuous signal can be approximated by employing the discrete Fourier transform to sampled spectral data. A deep understanding of function approximation by Fourier representations is even more crucial for deriving more advanced transforms as the nonequispaced fast Fourier transform, which is an approximative algorithm by nature, or sparse fast Fourier transforms on special lattices in higher dimensions.

This book encompasses the required classical Fourier theory in the first part in order to give deep insights into the construction and analysis of corresponding fast Fourier algorithms in the second part, including recent developments on nonequispaced and sparse fast Fourier transforms in higher dimensions. In the third part of the book, we present a selection of mathematical applications including recent research results on nonlinear function approximation by exponential sums. Our book starts with two chapters on classical Fourier analysis and Chap. 3 on the discrete Fourier transform in one dimension, followed by Chap. 4 on the multivariate case. This theoretical part provides the background for all further chapters and makes the book self-contained. Chapters 5–8 are concerned with the construction and analysis of corresponding fast algorithms in the one- and multidimensional case. While Chap. 5 covers the well-known fast Fourier transforms, Chaps. 7 and 8 are concerned with the construction of the nonequispaced fast Fourier transforms and the high-dimensional fast Fourier transforms on special lattices.

Chapter 6 is devoted to discrete trigonometric transforms and Chebyshev expansions which are closely related to Fourier series. The last part of the book contains two chapters on applications of numerical Fourier methods for improved function approximation. Starting with Sects. 5.4 and 5.5, the book covers many recent well-recognized developments in numerical Fourier analysis which cannot be found in other books in this form, including research results of the authors obtained within the last 20 years. This includes topics such as:

• The analysis of the numerical stability of the radix-2 FFT in Sect. 5.5
• Fast trigonometric transforms based on orthogonal matrix factorizations and fast discrete polynomial transforms in Chap. 6
• Fast Fourier transforms and fast trigonometric transforms for nonequispaced data in space and/or frequency in Sects. 7.1–7.4
• Fast summation at nonequispaced knots in Sect. 7.5 More recent research results can be found on: • Sparse FFT for vectors with presumed sparsity in Sect. 5.4
• High-dimensional sparse fast FFT on rank-1 lattices in Chap. 8
• Applications of multi-exponential analysis and Prony method for recovery of structured functions in Chap. 10

An introductory course on Fourier analysis at the advanced undergraduate level can for example be built using Sects. 1.2–1.4, 2.1–2.2, 3.2–3.3, 4.1–4.3, and 5.1– 5.2. We assume that the reader is familiar with basic knowledge on calculus of univariate and multivariate functions (including basic facts on Lebesgue integration and functional analysis) and on numerical linear algebra. Focusing a lecture on discrete fast algorithms and applications, one may consult Chaps. 3, 5, 6, and 9. Chapters 7, 8, and 10 are at an advanced level and require pre-knowledge from Chaps. 1, 2, and 4.

Parts of the book are based on a series of lectures and seminars given by the authors to students of mathematics, physics, computer science, and electrical engineering. Chapters 1, 2, 3, 5, and 9 are partially based on teaching material written by G. Steidl and M. Tasche that was published in 1996 by the University of Hagen under the title “Fast Fourier Transforms—Theory and Applications” (in German).