4
$\begingroup$

Hi, everyone! Is there any efficient way to simplify the following tensor product

$X \otimes X + X^T \otimes X^T$, where $X$ is a square $n \times n$ matrix.

My goal is to efficiently compute the dominant eigenvector of $X \otimes X + X^T \otimes X^T$. However, the direct way is computationally expensive. Is it possible to simplify it avoid tensor computation.

For example, to compute the dominant eigenvector of $X \otimes X$, i can compute the dominant eigenvector of $X$ first, denoted by $v$. Then i only need to compute $v \cdot v^T$, which is the dominant eigenvector of $X \otimes X$. However, when it comes to $X \otimes X + X^T \otimes X^T$, i have no idea. Could anyone give me some suggestion or reference? Thank you in advance!

Improve this question
$\endgroup$
1
  • $\begingroup$ PS: My initial intuition is to avoid using tensor product when computing $X \otimes X$. Hence, a naive idea is to rewrite the dominant eigenvector $X \otimes X +X^T \otimes X^T$ in term of the dominant eigenvector $X$ or that of $X+X^T$, $X \cdot X^T$ and so forth, but i'm not sure whether it is feasible. $\endgroup$
    – person
    Commented Feb 4, 2011 at 9:17

1 Answer 1

Reset to default
1
$\begingroup$

In general, there is no simple way to relate the eigenvalues of a sum to the eigenvalues of the original matrices.

What you can do computationally is switching to iterative algorithms (Arnoldi method; eigs in Matlab, scipy.sparse.linalg.eigs, or the library Arpack if you are stuck with Fortran/C++). In this way, the computational cost is $O(M\cdot steps)$, where $steps$ is the number of steps needed (usually moderate, if the dominant eigenvalue is well-separated and/or you only need a small number of significant digits), and $M$ is the cost of a matrix-vector multiplication with your matrix, which is easier in your case due to the simple tensor product structure. You will need to code a subroutine for the map $v\mapsto Mv$.

(This is generally a good idea anyway if $n$ is large and you only need a small part of the spectrum.)

If the dominant eigenvalue is not well-separated, you have a computationally challenging problem, and you may want to visit your favorite numerical analyst for a more thorough diagnosis.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your kind help. Could you give any hint on how to avoid tensor product? $\endgroup$
    – person
    Commented Feb 4, 2011 at 9:18
  • $\begingroup$ First idea that comes into my mind: if your vector was in the form $a\otimes b$, then it would be easy to code the map $v\mapsto Mv$ without computing explicitly the tensor product. Since it is not, you may cheat and decompose it into the sum of $n$ vector of this kind, just take $a=e_1,e_2,\dots,e_n$. This should cost $O(n^2\cdot n)$ ops, assuming no structure on $X$. If $X$ is sparse or Toeplitz, well, you should've mentioned that from the start. :) Maybe someone else will come up with a better strategy though. $\endgroup$
    – Federico Poloni
    Commented Feb 4, 2011 at 22:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .