Optimal Kronecker Product Approximation of Block Toeplitz Matrices

J. Kamm and J. Nagy

This paper considers the problem of finding n-by-n matrices Ak and Bk that minimize ||T - sum(Ak (x) Bk||_F, where (x) denotes Kronecker product, and T is a banded n-by-n block Toeplitz matrix with banded n-by-n Toeplitz blocks. It is shown that the optimal Ak and Bk are banded Toeplitz matrices, and an efficient algorithm for computing the approximation is provided. An image restoration problem from the Hubble Space Telescope is used to illustrate the effectiveness of an approximate SVD preconditioner constructed from the Kronecker product decomposition.