Numerical Fourier Analysis (eBook)

ANHA Series Preface 6
Preface 9
Contents 12
1 Fourier Series 16
1.1 Fourier's Solution of Laplace Equation 16
1.2 Fourier Coefficients and Fourier Series 21
1.3 Convolution of Periodic Functions 31
1.4 Pointwise and Uniform Convergence of Fourier Series 42
1.4.1 Pointwise Convergence 45
1.4.2 Uniform Convergence 55
1.4.3 Gibbs Phenomenon 60
1.5 Discrete Signals and Linear Filters 66
2 Fourier Transforms 75
2.1 Fourier Transforms on L1(R) 75
2.2 Fourier Transforms on L2(R) 92
2.3 Poisson Summation Formula and Shannon's Sampling Theorem 97
2.4 Heisenberg's Uncertainty Principle 102
2.5 Fourier-Related Transforms in Time–Frequency Analysis 109
2.5.1 Windowed Fourier Transform 109
2.5.2 Fractional Fourier Transforms 115
3 Discrete Fourier Transforms 121
3.1 Motivations for Discrete Fourier Transforms 121
3.1.1 Approximation of Fourier Coefficients and Aliasing Formula 122
3.1.2 Computation of Fourier Series and Fourier Transforms 126
3.1.3 Trigonometric Polynomial Interpolation 128
3.2 Fourier Matrices and Discrete Fourier Transforms 132
3.2.1 Fourier Matrices 132
3.2.2 Properties of Fourier Matrices 138
3.2.3 DFT and Cyclic Convolutions 144
3.3 Circulant Matrices 151
3.4 Kronecker Products and Stride Permutations 156
3.5 Discrete Trigonometric Transforms 165
4 Multidimensional Fourier Methods 172
4.1 Multidimensional Fourier Series 172
4.2 Multidimensional Fourier Transforms 179
4.2.1 Fourier Transforms on S(Rd) 180
4.2.2 Fourier Transforms on L1(Rd) and L2(Rd) 189
4.2.3 Poisson Summation Formula 191
4.2.4 Fourier Transforms of Radial Functions 193
4.3 Fourier Transform of Tempered Distributions 196
4.3.1 Tempered Distributions 196
4.3.2 Fourier Transforms on S(Rd) 206
4.3.3 Periodic Tempered Distributions 212
4.3.4 Hilbert Transform and Riesz Transform 218
4.4 Multidimensional Discrete Fourier Transforms 226
4.4.1 Computation of Multivariate Fourier Coefficients 226
4.4.2 Two-Dimensional Discrete Fourier Transforms 230
4.4.3 Higher-Dimensional Discrete Fourier Transforms 239
5 Fast Fourier Transforms 244
5.1 Construction Principles of Fast Algorithms 244
5.2 Radix-2 FFTs 248
5.2.1 Sande–Tukey FFT in Summation Form 249
5.2.2 Cooley–Tukey FFT in Polynomial Form 252
5.2.3 Radix-2 FFT's in Matrix Form 255
5.2.4 Radix-2 FFT for Parallel Programming 260
5.2.5 Computational Costs of Radix-2 FFT's 263
5.3 Other Fast Fourier Transforms 266
5.3.1 Chinese Remainder Theorem 267
5.3.2 Fast Algorithms for DFT of Composite Length 269
5.3.3 Radix-4 FFT and Split–Radix FFT 276
5.3.4 Rader FFT and Bluestein FFT 282
5.3.5 Multidimensional FFTs 289
5.4 Sparse FFT 294
5.4.1 Single Frequency Recovery 295
5.4.2 Recovery of Vectors with One Frequency Band 298
5.4.3 Recovery of Sparse Fourier Vectors 301
5.5 Numerical Stability of FFT 308
6 Chebyshev Methods and Fast DCT Algorithms 317
6.1 Chebyshev Polynomials and Chebyshev Series 317
6.1.1 Chebyshev Polynomials 318
6.1.2 Chebyshev Series 324
6.2 Fast Evaluation of Polynomials 332
6.2.1 Horner Scheme and Clenshaw Algorithm 332
6.2.2 Polynomial Evaluation and Interpolation at Chebyshev Points 335
6.2.3 Fast Evaluation of Polynomial Products 342
6.3 Fast DCT Algorithms 345
6.3.1 Fast DCT Algorithms via FFT 346
6.3.2 Fast DCT Algorithms via Orthogonal Matrix Factorizations 350
6.4 Interpolation and Quadrature Using Chebyshev Expansions 360
6.4.1 Interpolation at Chebyshev Extreme Points 360
6.4.2 Clenshaw–Curtis Quadrature 369
6.5 Discrete Polynomial Transforms 377
6.5.1 Orthogonal Polynomials 377
6.5.2 Fast Evaluation of Orthogonal Expansions 379
7 Fast Fourier Transforms for Nonequispaced Data 389
7.1 Nonequispaced Data Either in Space or Frequency Domain 389
7.2 Approximation Errors for Special Window Functions 397
7.3 Nonequispaced Data in Space and Frequency Domain 406
7.4 Nonequispaced Fast Trigonometric Transforms 409
7.5 Fast Summation at Nonequispaced Knots 415
7.6 Inverse Nonequispaced Discrete Transforms 422
7.6.1 Direct Methods for Inverse NDCT and Inverse NDFT 423
7.6.2 Iterative Methods for Inverse NDFT 429
8 High-Dimensional FFT 432
8.1 Fourier Partial Sums of Smooth Multivariate Functions 433
8.2 Fast Evaluation of Multivariate Trigonometric Polynomials 438
8.2.1 Rank-1 Lattices 439
8.2.2 Evaluation of Trigonometric Polynomials on Rank-1 Lattice 441
8.2.3 Evaluation of the Fourier Coefficients 443
8.3 Efficient Function Approximation on Rank-1 Lattices 445
8.4 Reconstructing Rank-1 Lattices 448
8.5 Multiple Rank-1 Lattices 453
9 Numerical Applications of DFT 460
9.1 Cardinal Interpolation by Translates 460
9.1.1 Cardinal Lagrange Function 465
9.1.2 Computation of Fourier Transforms 475
9.2 Periodic Interpolation by Translates 479
9.2.1 Periodic Lagrange Function 480
9.2.2 Computation of Fourier Coefficients 486
9.3 Quadrature of Periodic Functions 489
9.4 Accelerating Convergence of Fourier Series 496
9.4.1 Krylov–Lanczos Method 497
9.4.2 Fourier Extension 501
9.5 Fast Poisson Solvers 506
9.6 Spherical Fourier Transforms 518
9.6.1 Discrete Spherical Fourier Transforms 521
9.6.2 Fast Spherical Fourier Transforms 522
9.6.3 Fast Spherical Fourier Transforms for Nonequispaced Data 524
9.6.4 Fast Quadrature and Approximation on S2 529
10 Prony Method for Reconstruction of Structured Functions 533
10.1 Prony Method 533
10.2 Recovery of Exponential Sums 539
10.2.1 MUSIC and Approximate Prony Method 541
10.2.2 ESPRIT 546
10.3 Stability of Exponentials 552
10.4 Recovery of Structured Functions 566
10.4.1 Recovery from Fourier Data 566
10.4.2 Recovery from Function Samples 571
10.5 Phase Reconstruction 577
A List of Symbols and Abbreviations 584
A.1 Table of Some Fourier Series 584
A.2 Table of Some Chebyshev Series 585
A.3 Table of Some Fourier Transforms 586
A.4 Table of Some Discrete Fourier Transforms 587
A.5 Table of Some Fourier Transforms of Tempered Distributions 588
Numbers and Related Notations 589
Periodic Functions and Related Notations 590
Sequences and Related Notations 591
Nonperiodic Functions Defined on R or Rd and Related Notations 591
Vectors, Matrices, and Related Notations 592
Real-Valued Functions Defined on [-1,1] and Related Notations 594
Abbreviations 595
References 597
Index 614
Applied and Numerical Harmonic Analysis (90 Volumes) 621