Abstract. Given two $n\times n$ Toeplitz matrices $T_1$ and $T_2$, and a vector $\B b\in\R^{n^2}$, consider the linear system $A\B x=\B b-\B \eta$, where $\B \eta\in\R^{n^2}$ is an unknown vector representing the noise and $A=T_1\otimes T_2$. Recovering approximations of $\B x$, given $A$ and $\B b$, is encountered in image restoration problems. We propose a method for the approximation of the solution $\B x$ that has good regularization properties. The algorithm is based on a modified version of Newton's iteration for matrix inversion and relies on the concept of approximate displacement rank. We provide a formal description of the regularization properties of Newton's iteration in terms of filters and determine bounds to the number of iterations that guarantee regularization. The method is extended to deal with more general systems where $A=\sum_{i=1}^h T^{(i)}_1\otimes T^{(i)}_2$. The cost of computing regularized inverses is $O(n\log n)$ operations (ops), the cost of solving the system $A\B x=\B b$ is $O(n^2\log n)$ ops. Numerical experiments which show the effectiveness of our algorithm are presented.

  <dvi>  <postscript>  files of the paper

Back to Beatrice Meini's home page.