A Sparse Data Fast Fourier Transform (SDFFT)

Alaeddin A. Aydiner, Weng Cho Chew, Tie Jun Cui, Jiming Song

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)3161-3170
Number of pages10
JournalIEEE Transactions on Antennas and Propagation
Issue number11
StatePublished - Nov 2003


  • Far-field computation
  • Multilevel algorithm
  • Nonuniform fast Fourier transform (NUFFT)
  • Parabolic reflector
  • Physical optics
  • Synthetic aperture radar imaging
  • Tomography

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'A Sparse Data Fast Fourier Transform (SDFFT)'. Together they form a unique fingerprint.

Cite this