Misha Kilmer
Tensor-diamond Approximation for Construction of Kronecker Product-based Preconditioners

Dept of Mathematics
Tufts University
503 Boston Ave
Medford
MA 02155
misha.kilmer@tufts.edu
Tamara Kolda

Tensor-diamond Approximation for Construction of Kronecker Product-based Preconditioners

Suppose ${\bf A}$ is a square, invertible, block $\ell \times \ell$ matrix with $n \times n$ blocks, that is characterized by either (or both) of the following conditions:

• ${\bf A}$ is block Toeplitz (or can be permuted to be block Toeplitz);
  
• ${\bf A}$ has small block-bandwidth $k \ll \ell$ (or, more generally, the number of non-zero blocks is much less than $\ell$ ).

Such matrices might arise, for example, in image deblurring or discretization of a PDE. In this talk, we will primarily focus on on image deblurring applications.

We consider the problem of determining an approximation ${\bf M}$ to ${\bf A}$ such that either

$${\bf M}= {\bf A}_R \otimes {\bf A}_L$$    or $$\qquad {\bf M}= ({\bf {\boldmath {\MakeUppercase{I}}}} \otimes {\bf A}_L){\bf {\boldmath {\MakeUppercase{C}}}},$$

where $\otimes$ denotes the Kronecker product, and ${\bf {\boldmath {\MakeUppercase{C}}}}$ is a matrix with circulant blocks. The leftmost problem has been studied previously (see, for example, [1,2]). Our approach differs from previous approaches in that we produce the desired factorization by representing the approximation problem as a third-order tensor (i.e. 3D array) approximation problem. In the context of PDEs, the approximation ${\bf M}$ has the advantage of being relatively easy to directly invert and therefore is attractive as a preconditioner. In the context of image deblurring, we can relatively easily compute rank-revealing factorizations of ${\bf M}$ , which can then be used to generate regularized preconditioners or surrogate filters, etc.

Specifically, we take the relevant descriptive information from ${\bf A}$ and put this into an appropriately oriented $n \times m \times n$ , third-order tensor, denoted $\boldsymbol{\cal {\MakeUppercase{A}}}$ . We then consider the tensor approximation problem

$$\min_{{\bf {\boldmath {\MakeUppercase{G}}}},{\bf {\boldmath {\Mak... ...akeUppercase{G}}}} \diamondsuit {\bf {\boldmath {\MakeUppercase{H}}}} \Vert _F,$$   with possible constraints on H$$,$$

where the ${\bf {\boldmath {\MakeUppercase{G}}}} \diamondsuit {\bf {\boldmath {\MakeUppercase{H}}}}$ is the product-cyclic tensor, first defined in [3], given by

$${\bf {\boldmath {\MakeUppercase{G}}}} \diamondsuit {\bf {\boldmat... ...\boldmath {\MakeUppercase{Z}}}}^{j-1} {\bf {\boldmath {\MakeUppercase{H}}}}^T,$$

and ${\bf {\boldmath {\MakeUppercase{Z}}}}$ is the $n \times n$ downshift matrix. We will discuss how the entries of ${\bf A}_L, {\bf A}_R$ or ${\bf A}_R, {\bf {\boldmath {\MakeUppercase{C}}}}$ are constructed from entries in ${\bf {\boldmath {\MakeUppercase{G}}}}$ and ${\bf {\boldmath {\MakeUppercase{H}}}}$ .

Numerical results for spatially variant blurring operators show the possible utility of this approach.

References:
[1] C. F. Van Loan and N. P. Pitsianis, ``Approximation with Kronecker Products," in Linear Algebra for Large Scale and Real Time Applications, Kluwer Publications, 1993, M. S. Moonen and G. H. Golub eds, pages 293-314.

[2] J. Kamm and J. G. Nagy, ``Optimal Kronecker Product Approximation of Block Toeplitz Matrices," SIAM Journal on Matrix Analysis and Applications, volume 22, 2000, pages 155-172.

[3] M. E. Kilmer and T. G. Kolda, ``Approximations of Third Order Tensors as Sums of (Non-negative) Product Cyclic Tensors," Plenary Presentation, Householder Symposium, June 2011.