Regularizing Inverse Preconditioners for Symmetric Band Toeplitz Matrices
- PDF / 661,961 Bytes
- 9 Pages / 600.03 x 792 pts Page_size
- 97 Downloads / 208 Views
Research Article Regularizing Inverse Preconditioners for Symmetric Band Toeplitz Matrices P. Favati,1 G. Lotti,2 and O. Menchi3 1 Istituto
di Informatica e Telematica (IIT), CNR, Via G. Moruzzi 1, 56124 Pisa, Italy di Matematica, Universit`a di Parma, Parco Area delle Scienze 53/A, 43100 Parma, Italy 3 Dipartimento di Informatica, Universit` a di Pisa, Largo Pontecorvo 3, 56127 Pisa, Italy 2 Dipartimento
Received 22 September 2006; Revised 31 January 2007; Accepted 16 March 2007 Recommended by Paul Van Dooren Image restoration is a widely studied discrete ill-posed problem. Among the many regularization methods used for treating the problem, iterative methods have been shown to be effective. In this paper, we consider the case of a blurring function defined by space invariant and band-limited PSF, modeled by a linear system that has a band block Toeplitz structure with band Toeplitz blocks. In order to reduce the number of iterations required to obtain acceptable reconstructions, in [1] an inverse Toeplitz preconditioner for problems with a Toeplitz structure was proposed. The cost per iteration is of O(n2 log n) operations, where n2 is the pixel number of the 2D image. In this paper, we propose inverse preconditioners with a band Toeplitz structure, which lower the cost to O(n2 ) and in experiments showed the same speed of convergence and reconstruction efficiency as the inverse Toeplitz preconditioner. Copyright © 2007 P. Favati et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1.
INTRODUCTION
Many image restoration problems can be modeled by the linear system Ax = b − w,
(1)
where x, b, and w represent the original image, the observed image, and the noise, respectively. Matrix A is defined by the so-called point spread function (PSF), which describes how the image is blurred out. If the PSF is space invariant with respect to translation, that is, a single pixel is blurred independently of its location, and is bandlimited, that is, it has a local action, matrix A turns out to have a band block Toeplitz structure with band Toeplitz blocks (hereafter band BTTB structure). Since A is generally ill-conditioned, the exact solution of the system Ay = b
(2)
may differ considerably from x even if w is small, and a regularized solution of (1) is sought. A widely used regularization technique [2–4] suggests solving (2) by employing the
conjugate gradient (CG) method when A is positive definite or some of its generalizations for the nonpositive definite case. In fact, CG is a semiconvergent method: at first the iteration reconstructs the low frequency components of the original signal, then subsequently, the iteration also starts to recover increasing frequency components, corresponding to the noise. Thus the iteration must be stopped when the noise components start to interfere. A general purpose preconditioner, which reduces the condition number
Data Loading...
