New technological innovations and advances in research in areas such as spectroscopy, computer tomography, signal processing, and data analysis require a deep understanding of function approximation using Fourier methods. To address this growing need, this monograph combines mathematical theory and numerical algorithms to offer a unified and self-contained presentation of Fourier analysis.
The first four chapters of the text serve as an introduction to classical Fourier analysis in the univariate and multivariate cases, including the discrete Fourier transforms, providing the necessary background for all further chapters. Next, chapters explore the construction and analysis of corresponding fast algorithms in the one- and multidimensional cases. The well-known fast Fourier transforms (FFTs) are discussed, as well as recent results on the construction of the nonequispaced FFTs, high-dimensional FFTs on special lattices, and sparse FFTs. An additional chapter is devoted to discrete trigonometric transforms and Chebyshev expansions. The final two chapters consider various applications of numerical Fourier methods for improved function approximation, including Prony methods for the recovery of structured functions.
This new edition has been revised and updated throughout, featuring new material on a new Fourier approach to the ANOVA decomposition of high-dimensional trigonometric polynomials; new research results on the approximation errors of the nonequispaced fast Fourier transform based on special window functions; and the recently developed ESPIRA algorithm for recovery of exponential sums, among others.
Numerical Fourier Analysis will be of interest to graduate students and researchers in applied mathematics, physics, computer science, engineering, and other areas where Fourier methods play an important role in applications.
Author(s): Gerlind Plonka , Daniel Potts , Gabriele Steidl , Manfred Tasche
Series: Applied and Numerical Harmonic Analysis
Edition: 2
Publisher: Birkhäuser
Year: 2023
Language: English
Pages: 664
City: Cham
Tags: Numerical Fourier Analysis, Discrete Fourier Transforms, Fast Fourier Transforms, Multidimensional Fourier Methods, High-dimensional FFT, Fast DCT Methods, FFT for Nonequispaced Data, Prony Methods
ANHA Series Preface
Preface to the Second Edition
Preface to the First Edition
Contents
1 Fourier Series
1.1 Fourier's Solution of Laplace Equation
1.2 Fourier Coefficients and Fourier Series
1.3 Convolution of Periodic Functions
1.4 Pointwise and Uniform Convergence of Fourier Series
1.4.1 Pointwise Convergence
1.4.2 Uniform Convergence
1.4.3 Gibbs Phenomenon
1.5 Discrete Signals and Linear Filters
2 Fourier Transform
2.1 Fourier Transform on L1(R)
2.2 Fourier Transform on L2(R)
2.3 Poisson Summation Formula and Shannon's Sampling Theorem
2.4 Heisenberg's Uncertainty Principle
2.5 Fourier-Related Transforms in Time–Frequency Analysis
2.5.1 Windowed Fourier Transform
2.5.2 Fractional Fourier Transforms
3 Discrete Fourier Transforms
3.1 Motivations for Discrete Fourier Transforms
3.1.1 Approximation of Fourier Coefficients and Aliasing Formula
3.1.2 Computation of Fourier Series and Fourier Transforms
3.1.3 Trigonometric Polynomial Interpolation
3.2 Fourier Matrices and Discrete Fourier Transforms
3.2.1 Fourier Matrices
3.2.2 Properties of Fourier Matrices
3.2.3 DFT and Cyclic Convolutions
3.3 Circulant Matrices
3.4 Kronecker Products and Stride Permutations
3.5 Discrete Trigonometric Transforms
4 Multidimensional Fourier Methods
4.1 Multidimensional Fourier Series
4.2 Multidimensional Fourier Transform
4.2.1 Fourier Transform on S(Rd)
4.2.2 Fourier Transforms on L1(Rd) and L2(Rd)
4.2.3 Poisson Summation Formula
4.2.4 Fourier Transforms of Radial Functions
4.3 Fourier Transform of Tempered Distributions
4.3.1 Tempered Distributions
4.3.2 Fourier Transforms on S(Rd)
4.3.3 Periodic Tempered Distributions
4.3.4 Hilbert Transform and Riesz Transform
4.4 Fourier Transform of Measures
4.4.1 Measure Spaces
4.4.2 Fourier Transform of Measures on Td
4.4.3 Fourier Transform of Measures on Rd
4.5 Multidimensional Discrete Fourier Transforms
4.5.1 Computation of Multivariate Fourier Coefficients
4.5.2 Two-Dimensional Discrete Fourier Transforms
4.5.3 Higher-Dimensional Discrete Fourier Transforms
5 Fast Fourier Transforms
5.1 Construction Principles of Fast Algorithms
5.2 Radix–2 FFTs
5.2.1 Sande–Tukey FFT in Summation Form
5.2.2 Cooley–Tukey FFT in Polynomial Form
5.2.3 Radix–2 FFT in Matrix Form
5.2.4 Radix–2 FFT for Parallel Programming
5.2.5 Computational Cost of Radix–2 FFT
5.3 Other Fast Fourier Transforms
5.3.1 Chinese Remainder Theorem
5.3.2 Fast Algorithms for DFT of Composite Length
5.3.3 Radix–4 FFT and Split–Radix FFT
5.3.4 Rader FFT and Bluestein FFT
5.3.5 Multidimensional FFT
5.4 Sparse FFT
5.4.1 Single-Frequency Recovery
5.4.2 Recovery of Vectors with One Frequency Band
5.4.3 Recovery of Sparse Fourier Vectors
5.5 Numerical Stability of FFT
6 Chebyshev Methods and Fast DCT Algorithms
6.1 Chebyshev Polynomials and Chebyshev Series
6.1.1 Chebyshev Polynomials
6.1.2 Chebyshev Series
6.2 Fast Evaluation of Polynomials
6.2.1 Horner Scheme and Clenshaw Algorithm
6.2.2 Polynomial Evaluation and Interpolation at Chebyshev Points
6.2.3 Fast Evaluation of Polynomial Products
6.3 Fast DCT Algorithms
6.3.1 Fast DCT Algorithms via FFT
6.3.2 Fast DCT Algorithms via Orthogonal Matrix Factorizations
6.3.3 Fast Two-Dimensional DCT Algorithms
6.4 Interpolation and Quadrature Using Chebyshev Expansions
6.4.1 Interpolation at Chebyshev Extreme Points
6.4.2 Clenshaw–Curtis Quadrature
6.5 Discrete Polynomial Transforms
6.5.1 Orthogonal Polynomials
6.5.2 Fast Evaluation of Orthogonal Expansions
7 Fast Fourier Transforms for Nonequispaced Data
7.1 Nonequispaced Data Either in Space or Frequency Domain
7.2 Approximation Errors for Special Window Functions
7.3 Nonequispaced Data in Space and Frequency Domain
7.4 Nonequispaced Fast Trigonometric Transforms
7.5 Fast Summation at Nonequispaced Knots
7.6 Inverse Nonequispaced Discrete Transforms
7.6.1 Direct Methods for Inverse NDCT and Inverse NDFT
7.6.2 Iterative Methods for Inverse NDFT
8 High-Dimensional FFT
8.1 Fourier Partial Sums of Smooth Multivariate Functions
8.2 Fast Evaluation of Multivariate Trigonometric Polynomials
8.2.1 Rank-1 Lattices
8.2.2 Evaluation of Trigonometric Polynomials on Rank-1 Lattice
8.2.3 Evaluation of the Fourier Coefficients
8.3 Efficient Function Approximation on Rank-1 Lattices
8.4 Reconstructing Rank-1 Lattices
8.5 Multiple Rank-1 Lattices
9 Numerical Applications of DFT
9.1 Cardinal Interpolation by Translates
9.1.1 Cardinal Lagrange Function
9.1.2 Computation of Fourier Transforms
9.2 Periodic Interpolation by Translates
9.2.1 Periodic Lagrange Function
9.2.2 Computation of Fourier Coefficients
9.3 Quadrature of Periodic Functions
9.4 Accelerating Convergence of Fourier Series
9.4.1 Krylov–Lanczos Method
9.4.2 Fourier Extension
9.5 Fast Poisson Solvers
9.6 Spherical Fourier Transforms
9.6.1 Discrete Spherical Fourier Transforms
9.6.2 Fast Spherical Fourier Transforms
9.6.3 Fast Spherical Fourier Transforms for Nonequispaced Data
9.6.4 Fast Quadrature and Approximation on S2
10 Prony Method for Reconstruction of Structured Functions
10.1 Prony Method
10.2 Recovery of Exponential Sums
10.2.1 MUSIC and Approximate Prony Method
10.2.2 ESPRIT
10.2.3 ESPIRA
10.3 Stability of Exponentials
10.4 Recovery of Structured Functions
10.4.1 Recovery from Fourier Data
10.4.2 Recovery from Function Samples
10.5 Phase Reconstruction
A List of Symbols and Abbreviations
Numbers and Related Notations
Periodic Functions and Related Notations
Sequences and Related Notations
Nonperiodic Functions Defined on Rd and Related Notations
Vectors, Matrices, and Related Notations
Real-Valued Functions Defined on [-1,1] and Related Notations
Abbreviations
A.1 Table of Some Fourier Series
A.2 Table of Some Chebyshev Series
A.3 Table of Some Fourier Transforms
A.4 Table of Some Discrete Fourier Transforms
A.5 Table of Some Fourier Transforms of Tempered Distributions
References
Index
Applied and Numerical Harmonic Analysis (106 Volumes)
