Kronecker Product and SVD Approximations in Image Restoration

J. Kamm and J. Nagy

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 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, 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.