Fast Fourier transform: algorithms and applications (Q978560): Difference between revisions

The fast Fourier transform (FFT) is an essential tool in applied mathematics and digital signal processing. Excellent descriptions of the mathematical background of FFT can be found in the books by \textit{C.F.~Van Loan} [Computational frameworks for the fast Fourier transform, Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics (1992; Zbl 0757.65154)] and by \textit{R.~Tolimieri}, \textit{M.~An} and \textit{C. Lu} [Algorithms for discrete Fourier transform and convolution, 2nd ed. New York, NY: Springer (1997; Zbl 0894.65076)]. This monograph on the FFT is mainly written for graduate students and researchers in engineering and science. It consists of 8 chapters, 8 appendices and a comprehensive bibliography. After an extremely short introduction, Chapter 2 describes the properties of the discrete Fourier transform (DFT). Chapter 3 presents different FFTs such as decimation-in-time, decimation-in-frequency, radix-2, radix-3, radix-4, split-radix, and mixed-radix algorithms. The close connection between FFT and sparse factorization of the Fourier matrix is described too. The numerical stability of FFT is not discussed. Chapter 4 is devoted to integer FFT which is an integer approximation of the DFT. The integer FFT can be implemented by using only bit shifts and additions but no multiplications. Corresponding error estimates are missing. Chapter 5 presents properties of the 2- and 3-dimensional DFT and applications to filtering. Fast algorithms for the 2-dimensional DFT are covered in Chapter 6. The nonuniform DFT which is a DFT for nonequally spaced samples or frequencies is introduced in Chapter 7. The corresponding algorithms for the nonuniform DFT are very slow. The authors do not handle efficient algorithms of nonuniform DFT [see \textit{A.~Dutt} and \textit{V.~Rokhlin}, SIAM J.~Sci.~Comput. 14, No.~6, 1368--1393 (1993; Zbl 0791.65108)]. In Chapter 8, the authors sketch numerous applications of FFT in signal and image processing. Here the reader can find many useful suggestions for further applications of FFT. The appendices describe the performance comparison of transforms, spectral distance measures of image quality, the integer discrete cosine transform, discrete cosine and sine transforms, Kronecker products of matrices, mathematical relations, and basics of \texttt{MATLAB}. Each of the chapters 2--8 closes with a short summary and some exercises. The theory is explained by numerous examples, flow diagrams and figures. MATLAB programs are presented for many algorithms. This book provides a very useful reference for any engineer working in signal processing. Reviewer's remark: Unfortunately, the book contains many mathematical imprecisions. Some mathematical notions (such as unitary matrix, orthogonal matrix, permutation matrix, nonnegative remainder modulo \(N\), Laplacian of a matrix, singular matrix, \(\ldots\)) are not explained or used in a correct way. The Fourier matrix defined on p.~12 is scaled unitary, but not unitary. ``The matrix norm is greater than one for all matrices'' (cf.~p.~216), but the authors mean that the condition number of an invertible matrix is \(\geq 1\). A line of p.~372 is not readable. Further, almost all page numbers in the subject index are wrong.