Accurate and fast discrete polar Fourier transform

In this article we develop a fast high accuracy polar FFT. For a given two-dimensional signal of size N×N, the proposed algorithm´s complexity is O(N² log N), just like in a Cartesian 2D-FFT. A special feature of our approach is that it involves only 1-D equispaced FFT´s and 1D interpolations. A central tool in our approach is the pseudopolar FFT, an FFT where the evaluation frequencies lie in an over-sampled set of nonangularly equispaced points. The pseudopolar FFT plays the role of a halfway point-a nearly-polar system from which conversion to polar coordinates uses processes relying purely on interpolation operations. We describe the conversion process, and compare accuracy results obtained by unequally-sampled FFT methods to ours and show marked advantage to our approach.