.png){kind=icon}
Return
SPARSE FOURIER TRANSFORM VIA BUTTERFLY ALGORITHM
.png){kind=icon}
OA
AI
DOI：10.1137/08071291X.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper introduces a fast algorithm for computing sparse Fourier transforms with spatial and Fourier data supported on curves or surfaces. This problem appears naturally in several important applications of wave scattering, digital signal processing, and reflection seismology. The main idea of the algorithm is that the interaction between a frequency region and a spatial region is approximately low rank if the product of their widths are bounded by the maximum frequency. Based on this property, we can approximate the interaction between these two boxes accurately and compactly using a small number of equivalent sources. The overall structure of the algorithm follows the butterfly algorithm. The computation is further accelerated by exploiting the tensor-product property of the Fourier kernel in two and three dimensions. The proposed algorithm is accurate and has the optimal complexity. We present numerical results in both two and three dimensions.
Keywords:
Fourier transform
butterfly algorithm
multiscale methods
far field pattern
Journal
IF:
2.6
Papers:
5.1K
Citations:
1.8W
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSave
View more