Nonlinear image restoration finds applications in a wide variety of research areas. In this paper, we consider nonlinear space-invariant imaging system with additive noise. The restored images can be found by solving weighted Toeplitz least squares problems. Since the normal equations matrices are non-Toeplitz in general, the fast Fourier transforms (FFTs) cannot be utilized in the evaluation of their inverses. We employ the preconditioned conjugate gradient method (PCG) with the FFT-based preconditioners to solve regularized linear systems arising from nonlinear image restoration problems. Thus we precondition these linear systems in the Fourier domain, while iterating in the spatial domain. Numerical examples are reported on a ground-based atmospheric imaging problem to demonstrate the fast convergence of the FFT-based PCG method.