In this paper we propose an approach to approximate a truncated singular value decomposition of a large structured matrix. By first decomposing the matrix into a sum of Kronecker products, our approach can be used to approximate a large number of singular values and vectors more efficiently than other well known schemes, such as randomized matrix algorithms or iterative algorithms based on Golub-Kahan bidiagonalization. We provide theoretical results and numerical experiments to demonstrate the accuracy of our approximation and show how the approximation can be used to solve large scale ill-posed inverse problems, either as an approximate filtering method, or as a preconditioner to accelerate iterative algorithms.
The original idea of performing efficient Kronecker product decompositions on blur operator matrices came from Nagy in 1996 @cite_32 . This became the basis for a method to compute an approximated SVD by Kamm and Nagy @cite_1 . The same authors later provided theoretical justification for the method @cite_4 . The original algorithm applied only to block Toeplitz matrices with Toeplitz blocks corresponding to zero or periodic boundary conditions and only to 2D problems. Additionally, the original algorithm uses a simple computation for the singular value matrix @math as detailed in , although @cite_4 uses an additional diagonal weighting matrix in its construction.
@cite_1 @cite_32 @cite_4
2081500313 2155893732
Abstract Image restoration applications often result in ill-posed least squares problems involving large, structured matrices. One approach used extensively is to restore the image in the frequency domain, thus providing fast algorithms using fast Fourier transforms (FFTs). This is equivalent to using a circulant approximation to a given matrix. Iterative methods may also be used effectively by exploiting the structure of the matrix. While iterative schemes are more expensive than FFT-based methods, it has been demonstrated that they are capable of providing better restorations. As an alternative, we propose an approximate singular value decomposition (SVD), which can be used in a variety of applications. Used as a direct method, the computed restorations are comparable to iterative methods but are computationally less expensive. In addition, the approximate SVD may be used with the generalized cross validation method to choose regularization parameters. It is also demonstrated that the approximate SVD can be an effective preconditioner for iterative methods. This paper considers the problem of finding n × n matrices Ak and Bk that minimize @math , where @math 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.