Approximating the Fourier Transform from Non-equispaced Discrete Samples

Abstract

We study the approximation of the Fourier transform of a function from finitely many samples. Departing from the equispaced setting, we sample the function at deterministic non-equispaced nodes obtained by transforming equispaced points on $[0,1]$ through the inverse cumulative distribution function of a probability density. This change of variables compactifies the real line, so that no truncation of the space domain is necessary. Combining an exact aliasing identity for the midpoint rule with stationary-phase estimates for the transformed oscillatory integrals, we derive deterministic error bounds for every frequency and in $L_p$. For functions with polynomial decay in space and frequency, an explicitly optimized density recovers the equispaced convergence rate, while an additional variance parameter substantially reduces the pre-asymptotic error constants. For (sub-)exponentially decaying functions a polynomially decaying density yields (sub-)exponential rates. Numerical experiments confirm the theory and demonstrate the reduced pre-asymptotic error compared with optimally scaled equispaced sampling.