Optimal Kronecker Product Approximation of Block Toeplitz Matrices

This paper considers the problem of finding n × n matrices Ak and Bk that minimize ||T - ∑ Aₖ ⊗ Bₖ||F, where ⊗ denotes Kronecker product and T is a banded n × n block Toeplitz matrix with banded n × 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 (HST) is used to illustrate the effectiveness of an approximate SVD preconditioner constructed from the Kronecker product decomposition.