Fast and accurate polar Fourier transform (Q849677)

A fast high accuracy polar fast Fourier transform (FFT) is developed. Consider a polar grid of frequencies \( \xi_{p,q} = \{\xi_x [p,q], \xi_y [p,q]\}\) in the circle inscribed in the fundamental region \(\xi \in [-\pi, \pi)^2 ,\) \[ \begin{cases} \xi_x [p,q]= {\pi p\over N}\cos (\pi q/2N) \\ & \text{ for }-N \leq p \leq N-1,\quad 0 \leq q \leq 2N-1 \\ \xi_y [p,q]= {\pi p\over N} \sin (\pi q/2N) \end{cases}. \] Given digital Cartesian data \( f [i_1, i_2], \; i_1, i_2 = 0, \ldots , N-1, \) the polar FT is defined to be the collection of samples \(\{F(\xi_{p,q})\}\), where \[ F(\xi_{p,q}) = \sum^{N-1}_{i_1=0}\;\sum^{N-1}_{i_2 =0} f[i_1,i_2]\;\exp(-i(i_1 \xi_x [p,q]-i_2 \;\xi_y ]p,q])). \] The proposed method for the fast evaluation of \(\{F (\xi_{p,q} ) \}\) factors the problem into two steps. First, a pseudo-polar FFT is applied, in which a pseudo-polar sampling set is used, and second, a conversion from pseudo-polar to polar FT is performed by univariate polynomial interpolations. The pseudo-polar FFT is an FFT where the evaluation frequencies lie in an oversampled set of nonangularly equispaced points. For a given \(N \times N\) signal the proposed algorithm has an arithmetical complexity of \({\mathcal O} (N^2 \log N)\). Further, the conversion process is described and an error analysis is given.