zbMATH — the first resource for mathematics

FFT-based preconditioners for Toeplitz-block least squares problems. (English) Zbl 0793.65029
This interesting paper presents a comprehensive development of preconditioners for Toeplitz-block least squares problems, as those arising in two-dimensional deconvolution.
One and two-dimensional preconditioners using T. Chan’s circulant approximation to Toeplitz matrices [SIAM J. Sci. Stat. Comput. 9, No. 4, 766-771 (1988; Zbl 0646.65042)] are defined for the least squares problem. The advantage of using this type of approximation is that its spectrum can be economically calculated using fast Fourier transforms (FFT’s), which in turn can be used to obtain a pre-conditioned matrix with singular values clustered around 1, a most favorable situation for the convergence of the conjugate gradient method.
A complete error and complexity analysis makes the bulk of the paper, which is crown with a discussion of applications to two-dimensional deconvolution problems arising in imaging restoration, including some very promising preliminary numerical results.

65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F35 Numerical computation of matrix norms, conditioning, scaling
Full Text: DOI