A nonuniform fast Fourier transform based on low rank approximation

2017/01/17 by Ruiz-Antolin, Diego, Townsend, Alex · 1 citation
#FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.1701.04492

Abstract

By viewing the nonuniform discrete Fourier transform (NUDFT) as a perturbed version of a uniform discrete Fourier transform, we propose a fast, stable, and simple algorithm for computing the NUDFT that costs O(Nlog Nlog(1/ε)/log log(1/ε)) operations based on the fast Fourier transform, where N is the size of the transform and 0

Cited by

• A Superfast Direct Solver for Type-III Inverse Nonuniform Discrete Fourier Transform

Related

• Discrete Fourier Transform Approximations Based on the Cooley-Tukey Radix-2 Algorithm
• Non-iterative Type 4 and 5 Nonuniform FFT Methods in the One-Dimensional Case
• A parallel non-uniform fast Fourier transform library based on an\n "exponential of semicircle" kernel
• A Nonuniform Fast Hankel Transform
• A Superfast Direct Solver for Type-III Inverse Nonuniform Discrete Fourier Transform