  Circulant preconditioners are commonly used to accelerate the rate of
convergence of iterative methods when solving linear systems of equations with
a Toeplitz matrix. Block extensions that can be applied when the system has a
block Toeplitz matrix with Toeplitz blocks also have been developed. This paper
is concerned with preconditioning of linear systems of equations with a
symmetric block Toeplitz matrix with symmetric Toeplitz blocks that stem from
the discretization of a linear ill-posed problem. The right-hand side of the
linear systems represents available data and is assumed to be contaminated by
error. These kinds of linear systems arise, e.g., in image deblurring problems.
It is important that the preconditioner does not affect the invariant subspace
associated with the smallest eigenvalues of the block Toeplitz matrix to avoid
severe propagation of the error in the right-hand side. A perturbation result
indicates how the dimension of the subspace associated with the smallest
eigenvalues should be chosen and allows the determination of a suitable
preconditioner when an estimate of the error in the right-hand side is
available. This estimate also is used to decide how many iterations to carry
out by a minimum residual iterative method. Applications to image restoration
are presented.
