Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
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. –  person Feb 4 '11 at 9:17

1 Answer 1

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.

share|improve this answer
    
Thank you for your kind help. Could you give any hint on how to avoid tensor product? –  person Feb 4 '11 at 9:18
    
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. –  Federico Poloni Feb 4 '11 at 22:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.