Fast Fourier transform of sparse spatial data to sparse Fourier data

The nonuniform fast Fourier transform (FFT) on a line has been of interest to a number of scientists for its practical applications. However, not much has been written on Fourier transforming sparse spatial data where the Fourier transform is needed at only sparse data points in the Fourier space in 2D or 3D. It finds applications in remote sensing, inverse problems, and synthetic aperture radar where the scattered field is related to the Fourier transform of the scatterers. We outline an algorithm to perform this transform in NlogN operations, where N is the number of spatial data available, and we assume that the number of Fourier data desired is also of O(N). The algorithm described here is motivated by the multilevel fast multipole algorithm (MLFMA), but is different from that described by Brandt (1991). In MLFMA, an embedded fast Fourier transform algorithm is inherent, where the spatial data is arbitrarily distributed, but the Fourier data is required on the Ewald sphere. In the present algorithm, the restriction of the Fourier data to an Ewald sphere is lifted so that it can be arbitrarily distributed as well. The present algorithm can be easily generalized to 3D.