Plonka / Potts / Steidl Numerical Fourier Analysis

1. Auflage 2019
ISBN: 978-3-030-04306-3
Verlag: Springer International Publishing
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 624 Seiten

Reihe: Applied and Numerical Harmonic Analysis

This book offers a unified presentation of Fourier theory and corresponding algorithms emerging from new developments in function approximation using Fourier methods. It starts with a detailed discussion of classical Fourier theory to enable readers to grasp the construction and analysis of advanced fast Fourier algorithms introduced in the second part, such as  nonequispaced  and sparse FFTs in higher dimensions. Lastly, it contains a selection of numerical applications, including recent research results on nonlinear function approximation by exponential sums. The code of most of the presented algorithms is available in the authors' public domain software packages. Students and researchers alike benefit from this unified presentation of Fourier theory and corresponding algorithms.

Autoren/Hrsg.

Plonka, Gerlind

Potts, Daniel

Steidl, Gabriele

Tasche, Manfred

Inhaltsverzeichnis

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