On the regularized solution of block banded block Toeplitz systems

Given two n×n Toeplitz matrices T 1 and T 2, and a vector b∈R n(2), consider the linear system Ax = b-η, where η∈R n(2) is an unknown vector representing the noise and A = T 1⊗T 2. Recovering approximations of x, given A and b, is encountered in image restoration problems. We propose a method for the approximation of the solution 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 = ∑ i = 1 hT 1 (i)⊗T 2 (i). The cost of computing regularized inverses is O(n log n) operations (ops), the cost of solving the system Ax = b is O(n 2 log n) ops. Numerical experiments which show the effectiveness of our algorithm are presented.