The Regular Fourier Matrices and Nonuniform Fast Fourier Transforms
Let \(m\in\mathbb{N}\) and let \(q\), \(N\) be even. Set \(w= \exp(2\pi i/mN)\). In this interesting paper, the authors present a fast Fourier transform for unequally spaced data and equidistant frequencies \[ f_j= \sum^{N-1}_{k= 0}\alpha_k w^{jmc_k}\qquad (j=-N/2,\dots, N/2-1) \] with \(c_k\in [-N/2, N/2]\) and \(\alpha_k\in\mathbb{C}\). Note that usually \(m=2\), \(N\ll 1\), and \(q\approx- \log\varepsilon\), where \(\varepsilon\) is the precision. This method is based on a least-squares solution of a linear system related to the so-called regular Fourier matrix. It simplifies and improves the nonuniform fast Fourier transform of \textit{A. Dutt} and \textit{V. Rokhlin} [SIAM J. Sci. Comput. 14, No. 6, 1368-1393 (1993; Zbl 0791.65108)]. The total complexity of this algorithm is \(O(Nq^2- mN\log N)\).
- Fast Fourier transforms for nonequispaced data. II
- A new theoretical derivation of NFFT and its implementation on GPU
- Fourier series approximation of separable models
- Approximate factorizations of Fourier matrices with nonequispaced knots
- Fast algorithms for discrete polynomial transforms on arbitrary grids
- Joint image formation and two-dimensional autofocusing for synthetic aperture radar data
- Applications of Hankel and regular matrices in Fourier series
- Synthetic Aperture Radar Imaging
- On least squares discrete Fourier analysis of unequally spaced data
- scientific article; zbMATH DE number 1329498 (Why is no real title available?)
- Fast Fourier Transforms for Nonequispaced Data
- Dynamic MRI reconstruction from undersampled data with an anatomical prescan
- A nonuniform fast Fourier transform based on low rank approximation
- A solution to certain polynomial equations with applications to nonlinear fitting
- The Fourier approximation of smooth but non-periodic functions from unevenly spaced data
- The new operator marching method on calculating the electromagnetic scattered fields from the periodic structures
- scientific article; zbMATH DE number 7124329 (Why is no real title available?)
- A Frame Theoretic Approach to the Nonuniform Fast Fourier Transform
- Discrete orthogonal function expansions for non-uniform grids using the fast Fourier transform
- Fast and accurate polar Fourier transform
This page was built for publication: The Regular Fourier Matrices and Nonuniform Fast Fourier Transforms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4702381)