FFT-BASED PRECONDITIONERS FOR TOEPLITZ-BLOCK LEAST-SQUARES PROBLEMS

Discretized two-dimensional deconvolution problems arising, e.g., in i mage restoration and seismic tomography, can be formulated as least sq uares computations, min \\b - Tx\\2, where T is often a large-scale re ctangular Toeplitz-block matrix. The authors consider solving such blo ck least squares problems by the preconditioned conjugate gradient alg orithm using square nonsingular circulant-block and related preconditi oners, constructed from the blocks of the rectangular matrix T. Precon ditioning with such matrices allows efficient implementation using the one-dimensional or two-dimensional fast Fourier transform (FFT). Two- block preconditioners, related to those proposed by T. Chan and J. Olk in for square nonsingular Toeplitz-block systems, are derived and anal yzed. It is shown that, for important classes of T, the singular value s of the preconditioned matrix are clustered around one. This extends the authors' earlier work on preconditioners for Toeplitz least square s iterations for one-dimensional problems. It is well known that the r esolution of ill-posed deconvolution problems can be substantially imp roved by regularization to compensate for their ill-posed nature. It i s shown that regularization can easily be incorporated into our precon ditioners, and a report is given on numerical experiments on a Cray Y- MP. The experiments illustrate good convergence properties of these FF T-based preconditioned iterations.