3
$\begingroup$

Writing the SVDs of symmetric positive-definite matrices $A=U_AD_AU_A^T$ and $B=U_BD_BU_B^T$, the following inversion can conveniently be simplified: \begin{align*} (I + A \otimes B)^{-1} &= ((U_A \otimes U_B)(U_A \otimes U_B)^T + (U_A \otimes U_B)(D_A \otimes D_B)(U_A \otimes U_B)^T)^{-1} \\ &=(U_A \otimes U_B)(I + D_A \otimes D_B)^{-1}(U_A \otimes U_B)^T. \end{align*} That is, computing the inverse of $I + A \otimes B$ can be reduced to computing the SVDs of $A$ and $B$ and a cheap inversion of a diagonal matrix.

It is possible to similarly simplify $I + A \otimes B + C \otimes D$, where $A$, $B$, $C$, and $D$ are symmetric positive-definite matrices and the Kronecker products are compatible? That is, how can one favourably exploit the structure in $I + A \otimes B + C \otimes D$ in computing its inverse?

Edit: To clarify, for my particular use case, I am interested in computing $(I + A \otimes B + C \otimes D)^{-1} E$ for some matrix $E$; I don't necessarily need the inverse itself.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ do you need inverses or just need to solve a linear system? $\endgroup$
    – Suvrit
    Commented Mar 31, 2018 at 21:05
  • $\begingroup$ @Suvrit I need to solve a system, so anything that helps with that would help greatly. I'll add a remark to the question. $\endgroup$
    – user122652
    Commented Mar 31, 2018 at 21:33
  • 1
    $\begingroup$ In the case of a linear system, at least if you apply an iterative method, you can fully exploit the Kronecker structure; otherwise, I don't think that there is much one can do... $\endgroup$
    – Suvrit
    Commented Mar 31, 2018 at 23:47

1 Answer 1

Reset to default
3
$\begingroup$

Solving a linear system with that matrix is equivalent to solving the linear matrix equation $X + B^TXA + D^TXC = E$. As far as I know, it is an open problem how to exploit the structure of that matrix product to solve it (with a direct algorithm) in fewer than $O(n^5)$ operations (which is the complexity of $n^2$ steps of GMRES using the Kronecker structure to compute the products). It would be a big surprise to find a cheaper algorithm.

If one of the terms is small in norm or in rank, you can obtain a preconditioner for an iterative method by dropping it. That is currently your best bet to solve this problem. Pointers to some research in this direction: https://arxiv.org/abs/1704.02167, https://doi.org/10.1016/j.laa.2017.06.027.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, that is very helpful. Like the comment on the original question also says, applying an iterative method to exploit the Kronecker structure seems to be best one (currently, at least) can do. $\endgroup$
    – user122652
    Commented Apr 1, 2018 at 16:49

You must log in to answer this question.