The pseudo-polar Fourier transform is a fast algorithm that
samples the Fourier transform of an image on the concentric
squares grid. For some application we are given the samples of the
Fourier transform on this grid, and would like to recover the
original image. This arises, for example, in medical imaging
reconstruction problems. We develop two inversion algorithms for
the pseudo-polar Fourier transform: iterative and direct, both
with complexity $O(n^{2}\log{n})$, where $n \times n$ is the size
of the reconstructed image. The iterative algorithm is based on
the application of the conjugate-gradient method to the Gram
operator of the pseudo-polar Fourier transform. Since the
transform is ill-conditioned, we introduce a preconditioner, which
significantly accelerates the convergence. The direct inversion
algorithm utilizes the special frequency domain structure of the
transform in two steps. First, it resamples the pseudo-polar grid
to a Cartesian frequency grid, and then, recovers the image from
the Cartesian frequency grid.