A Frame Theoretic Approach to the Nonuniform Fast Fourier Transform

DOI10.1137/13092160XMaRDI QIDQ5254135zbMATH OpenOpenAlexFDO

Authors Anne Gelb, Guohui Song

Publication date 9 June 2015

Published in SIAM Journal on Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.3332

zbMATH Keywords

convolutional griddingFourier framesnonuniform fast Fourier transformnumerical frame approximation

Mathematics Subject Classification ID

Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16) Numerical methods for trigonometric approximation and interpolation (65T40) Numerical methods for discrete and fast Fourier transforms (65T50)

Abstract: Nonuniform Fourier data are routinely collected in applications such as magnetic resonance imaging, synthetic aperture radar, and synthetic imaging in radio astronomy. To acquire a fast reconstruction that does not require an online inverse process, the non-uniform fast Fourier transform (NFFT), also called convolutional gridding, is frequently employed. While various investigations have led to improvements in accuracy, efficiency, and robustness of the NFFT, not much attention has been paid to the fundamental analysis of the scheme, and in particular its convergence properties. This paper analyzes the convergence of the NFFT by casting it as a Fourier frame approximation. In so doing, we are able to design parameters for the method that satisfy conditions for numerical convergence. Our so called frame theoretic convolutional gridding algorithm can also be applied to detect features (such as edges) from non-uniform Fourier samples of piecewise smooth functions.

Recommendations

• A geometric nonuniform fast Fourier transform
• A nonuniform fast Fourier transform based on low rank approximation
• Accelerating the Nonuniform Fast Fourier Transform
• The Regular Fourier Matrices and Nonuniform Fast Fourier Transforms
• Nonuniform fast Fourier transforms with nonequispaced spatial and frequency data and fast sinc transforms
• Uniform error estimates for nonequispaced fast Fourier transforms
• scientific article; zbMATH DE number 5160955
• Theory, implementation and applications of nonstationary Gabor frames
• Fast Fourier transforms for nonequispaced data. II
• Optimized Least-Square Nonuniform Fast Fourier Transform

Cited in

(17)

• Finite Fourier frame approximation using the inverse polynomial reconstruction method
• Detecting edges from non-uniform Fourier data using Fourier frames
• Detecting edges from non-uniform Fourier data via sparse Bayesian learning
• Functional reproducing kernel Hilbert spaces for non-point-evaluation functional data
• Direct inversion of the nonequispaced fast Fourier transform
• The Nyquist sampling rate for spiraling curves
• A practical guide to the recovery of wavelet coefficients from Fourier measurements
• Recovering Piecewise Smooth Functions from Nonuniform Fourier Measurements
• The application of nonuniform fast Fourier transform for audio coding
• High-resolution 3-D radar imaging through nonuniform fast Fourier transform (NUFFT).
• Accelerating the Nonuniform Fast Fourier Transform
• PCM-TV-TFV: A Novel Two-Stage Framework for Image Reconstruction from Fourier Data
• Edge detection from non-uniform Fourier data using the convolutional gridding algorithm
• Sampling-based spotlight SAR image reconstruction from phase history data for Speckle reduction and uncertainty quantification
• A high-dimensional inverse frame operator approximation technique
• Generalized Fourier diffraction theorem and filtered backpropagation for tomographic reconstruction
• A hybrid reconstruction of piece-wise smooth functions from non-uniform Fourier data

Describes a project that uses

Uses Software

• NFFT3

This page was built for publication: A Frame Theoretic Approach to the Nonuniform Fast Fourier Transform

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5254135)