FFT-based preconditioners for Toeplitz-Block least square problems

Discretized two-dimensional deconvolution problems arising, e.g., in image restoration and seismic tomography, can be formulated as least squares computations, min [parallel] b [minus] Tx [parallel][sub 2], where T is often a large-scale rectangular Toeplitz-block matrix. The authors consider solvin...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on numerical analysis 1993-12, Vol.30:6
Main Authors: Chan, R.H., Nagy, J.G., Plemons, R.J.
Format: Article
Language:English
Subjects:
990200 - Mathematics & Computers
ALGORITHMS
COMPUTERS
CRAY COMPUTERS
FOURIER TRANSFORMATION
GENERAL AND MISCELLANEOUS//MATHEMATICS, COMPUTING, AND INFORMATION SCIENCE
IMAGE PROCESSING
INTEGRAL TRANSFORMATIONS
LEAST SQUARE FIT
MATHEMATICAL LOGIC
MAXIMUM-LIKELIHOOD FIT
NUMERICAL SOLUTION
PROCESSING
SEISMOLOGY
TRANSFORMATIONS
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Discretized two-dimensional deconvolution problems arising, e.g., in image restoration and seismic tomography, can be formulated as least squares computations, min [parallel] b [minus] Tx [parallel][sub 2], where T is often a large-scale rectangular Toeplitz-block matrix. The authors consider solving such block least squares problems by the preconditioned conjugate gradient algorithm using square nonsingular circulant-block and related preconditioners, constructed from the blocks of the rectangular matrix T. Preconditioning 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. Olkin for square nonsingular Toeplitz-block systems, are derived and analyzed. It is shown that, for important classes of T, the singular values of the preconditioned matrix are clustered around one. This extends the authors' earlier work on preconditioners for Toeplitz least squares iterations for one-dimensional problems. It is well known that the resolution of ill-posed deconvolution problems can be substantially improved by regularization to compensate for their ill-posed nature. It is shown that regularization can easily be incorporated into the preconditioners, and a report is given on numerical experiments on a Cray Y-MP. The experiments illustrate good convergence properties of these FFT-based preconditioned iterations.
ISSN:0036-1429
1095-7170
DOI:10.1137/0730089