An Exact And Fast Computation Of Discrete Fourier Transform For Polar And Spherical Grid

Keywords

2D imaging; 3D imaging; Block Toeplitz matrix; conjugate gradient method; discrete Fourier transform; fractional Fourier transform; hybrid grid; Nonuniform fourier transform; polar coordinates; spherical coordinates

Abstract

Numerous applied problems of two-dimensional (2-D) and 3-D imaging are formulated in continuous domain. They place great emphasis on obtaining and manipulating the Fourier transform in polar and spherical coordinates. However, the translation of continuum ideas with the discrete sampled data on a Cartesian grid is problematic. There exists no exact and fast solution to the problem of obtaining discrete Fourier transform for polar and spherical grids in the literature. In this paper, we develop exact algorithms to the above problem for 2-D and 3-D, which involve only 1-D equispaced fast Fourier transform with no interpolation or approximation at any stage. The result of the proposed approach leads to a fast solution with very high accuracy. We describe the computational procedure to obtain the solution in both 2-D and 3-D, which includes fast forward and inverse transforms. We find the nested multilevel matrix structure of the inverse process, and we propose a hybrid grid and use a preconditioned conjugate gradient method that exhibits a drastic improvement in the condition number.

Publication Date

4-15-2017

Publication Title

IEEE Transactions on Signal Processing

Volume

65

Issue

8

Number of Pages

2033-2048

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/TSP.2016.2645510

Socpus ID

85014969133 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85014969133

This document is currently not available here.

Share

COinS