TY - JOUR
T1 - A Sparse Data Fast Fourier Transform (SDFFT)
AU - Aydiner, Alaeddin A.
AU - Chew, Weng Cho
AU - Cui, Tie Jun
AU - Song, Jiming
N1 - Funding Information:
Manuscript received July 25, 2002; revised February 5, 2003. This work was supported in part by the Defense Advanced Research Projects Agency (DARPA) under Contract F49620-98-1-0498, by a MURI Grant F49620-96-1-0025 administered by the FOSR, and in part by the National Science Foundation (NSF) under Grant ECS99-06651.
PY - 2003/11
Y1 - 2003/11
N2 - A multilevel algorithm that efficiently Fourier transforms sparse spatial data to sparse spectral data with controllable error is presented. The algorithm termed "sparse data fast fourier transform" (SDFFT) is particularly useful for signal processing applications where only part of the k-space is to be computed - Regardless of whether it is a regular region like an angular section of the Ewald sphere or it consists of completely arbitrary points scattered in the k-space. In addition, like the various nonuniform fast Fourier transforms, the O(N log N) algorithm can deal with a sparse, nonuniform spatial domain. In this paper, the parabolic reflector antenna problem is studied as an example to demonstrate its use in the computation of far-field patterns due to arbitrary aperture antennas and antenna arrays. The algorithm is also promising for various applications such as back-projection tomography, diffraction tomography, and synthetic aperture radar imaging.
AB - A multilevel algorithm that efficiently Fourier transforms sparse spatial data to sparse spectral data with controllable error is presented. The algorithm termed "sparse data fast fourier transform" (SDFFT) is particularly useful for signal processing applications where only part of the k-space is to be computed - Regardless of whether it is a regular region like an angular section of the Ewald sphere or it consists of completely arbitrary points scattered in the k-space. In addition, like the various nonuniform fast Fourier transforms, the O(N log N) algorithm can deal with a sparse, nonuniform spatial domain. In this paper, the parabolic reflector antenna problem is studied as an example to demonstrate its use in the computation of far-field patterns due to arbitrary aperture antennas and antenna arrays. The algorithm is also promising for various applications such as back-projection tomography, diffraction tomography, and synthetic aperture radar imaging.
KW - Far-field computation
KW - Multilevel algorithm
KW - Nonuniform fast Fourier transform (NUFFT)
KW - Parabolic reflector
KW - Physical optics
KW - Synthetic aperture radar imaging
KW - Tomography
UR - http://www.scopus.com/inward/record.url?scp=0242527336&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0242527336&partnerID=8YFLogxK
U2 - 10.1109/TAP.2003.818792
DO - 10.1109/TAP.2003.818792
M3 - Article
AN - SCOPUS:0242527336
SN - 0018-926X
VL - 51
SP - 3161
EP - 3170
JO - IEEE Transactions on Antennas and Propagation
JF - IEEE Transactions on Antennas and Propagation
IS - 11
ER -