Optimal Kronecker product approximation of block Toeplitz matrices

This paper considers the problem of finding n x n matrices A(k) and B-k tha t minimize parallel to T - Sigma A(k) x B(k)parallel to(F), where x denotes Kronecker product and T is a banded n x n block Toeplitz matrix with bande d n x n Toeplitz blocks. It is shown that the optimal A(k) and B-k are band ed Toeplitz matrices, and an efficient algorithm for computing the approxim ation is provided. An image restoration problem from the Hubble Space Teles cope (HST) is used to illustrate the effectiveness of an approximate SVD pr econditioner constructed from the Kronecker product decomposition.