Large Least Squares Problems Involving Kronecker Products

Abstract

The general problem considered here is the least squares solution of $( A \otimes B )x = t$, where A and B are full rank, rectangular matrices, and $A \otimes B$ is the Kronecker product of A and B. Equations of this form arise in areas such as digital image and signal processing, photogrammetry, finite elements, and multidimensional approximation. An efficient method of solution is based on QR factorizations of the original matrices A and B. It is demonstrated how these factorizations can be used to obtain the Cholesky factorization of the least squares coefficient matrix without explicitly forming the normal equations. A similar approach based on singular value decomposition (SVD) factorizations also is indicated for the rank-deficient case.