The butterfly algorithm for synthetic aperture radar imaging

Laurent Demanet
Massachusetts Institute of Technology
Applied Mathematics

SAR image formation involves computing an oscillatory integral which looks like a distortion of a Fourier transform. FFT-based algorithms exist and are fast, but they tend to be inaccurate. I present an algorithmic alternative to the FFT, called the butterfly algorithm, to compute the SAR imaging integral to within prescribed accuracy, in complexity O(N log N) where N is the number of pixels.

Presentation (PDF File)

Back to Challenges in Synthetic Aperture Radar