next up previous
Next: About this document ...

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:

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

$\displaystyle {\bf M}= {\bf A}_R \otimes {\bf A}_L$    or $\displaystyle \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

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

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

$\displaystyle {\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.




next up previous
Next: About this document ...
root 2012-02-20