Numerical stability of nonequispaced fast Fourier transforms

DOI10.1016/j.cam.2007.12.025zbMath1210.65208MaRDI QIDQ955087

Daniel Potts, Manfred Tasche

Publication date: 18 November 2008

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cam.2007.12.025

zbMATH Keywords

algorithm; numerical examples; fast Fourier transform; numerical stability; roundoff error; nonequispaced data; sampling of trigonometric polynomials

Mathematics Subject Classification ID

65G50: Roundoff error

65T50: Numerical methods for discrete and fast Fourier transforms

65T40: Numerical methods for trigonometric approximation and interpolation

Related Items

Linear Stable Sampling Rate: Optimality of 2D Wavelet Reconstructions from Fourier Measurements, The Fourier approximation of smooth but non-periodic functions from unevenly spaced data, Parameter estimation for exponential sums by approximate prony method, Computing reconstructions from nonuniform Fourier samples: universality of stability barriers and stable sampling rates, Continuous window functions for NFFT, Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling, Weighted frames of exponentials and stable recovery of multidimensional functions from nonuniform Fourier samples

Uses Software

• mctoolbox

Cites Work

• Fast and accurate polar Fourier transform
• On the computation of the polar FFT
• A note on fast Fourier transforms for nonequispaced grids
• Efficient numerical methods in non-uniform sampling theory
• Non-equispaced fast Fourier transforms with applications to tomography
• On the fast Fourier transform of functions with singularities
• A new linogram algorithm for computerized tomography
• A probability argument in favor of ignoring small singular values
• Stability Results for Scattered Data Interpolation by Trigonometric Polynomials
• Reconstruction Algorithms in Irregular Sampling
• Fast Fourier Transforms for Nonequispaced Data
• Accelerating the Nonuniform Fast Fourier Transform
• Random Sampling of Multivariate Trigonometric Polynomials
• Accuracy and Stability of Numerical Algorithms
• Worst and average case roundoff error analysis for FFT
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item