Abstract

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.