Fast Fourier transform of sparse spatial data to sparse Fourier data

摘要

We have outlined an O(N log N) algorithm to Fourier transform sparse spatial data to sparse Fourier data. We assume that the data is dense in 1D both in spatial and Fourier space, but live in a 2D space. The algorithm can be easily generalized to higher dimensions. For nD problems it can be shown that the complexity remains O(N log N) when both the spatial and Fourier data are dense in αD where 0 <α