In the case of radial imaging with nonlinear spatial encoding fields, a prominent star-shaped artifact has been observed if a spin distribution is encoded with an undersampled trajectory. This work presents a new iterative reconstruction method based on the total generalized variation, which reduces this artifact. For this approach, a sampling operator (as well as its adjoint) is needed that maps data from PatLoc k-space to the final image space. It is shown that this can be realized as a type-3 nonuniform fast Fourier transform, which is implemented by a combination of a type-1 and type-2 nonuniform fast Fourier transform. Using this operator, it is also possible to implement an iterative conjugate gradient SENSE based method for PatLoc reconstruction, which leads to a significant reduction of computation time in comparison to conventional PatLoc image reconstruction methods. Results from numerical simulations and in vivo PatLoc measurements with as few as 16 radial projections are presented, which demonstrate significant improvements in image quality with the total generalized variation-based approach. Magn Reson Med, 2013. © 2012 Wiley Periodicals, Inc.