Hello,
If we possess the eigendecomposition of a positive definite matrix: $X = U \Sigma U^T$, is there an efficient way to compute the eigendecomposition of $D X D$ where $D$ is a diagonal matrix?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ Unless I'm missing something, the same $U$ works since diagonal matrices commute with everything... $\endgroup$– Paul SiegelCommented Jul 14, 2011 at 2:38
-
5$\begingroup$ Paul, that is only true if the diagonal matrix is scalar. $\endgroup$– MTSCommented Jul 14, 2011 at 3:41
-
$\begingroup$ :) If only it were that easy. Unfortunately a general diagonal matrix will change the eigenvalues and eigenvectors... It seems like there should be a way to update the eigendecomposition but I'm stumped. This is for an implementation of Gaussian belief propagation. First mathoverflow question--thanks for your thoughts. $\endgroup$– Martin McCormickCommented Jul 14, 2011 at 3:54
-
$\begingroup$ Now I'm definitely confused... are we not working over a field? What does positive definite mean over a noncommutative ring? $\endgroup$– Paul SiegelCommented Jul 14, 2011 at 12:49
-
3$\begingroup$ @Paul: diagonal matrices don't commute with everything, even on $\mathbb{Z}$: $\begin{bmatrix}1 & 1\\\\1 & 1 \end{bmatrix}\begin{bmatrix}2 & 0\\\\0 & 1 \end{bmatrix}\neq\begin{bmatrix}2 & 0\\\\0 & 1 \end{bmatrix} \begin{bmatrix}1 & 1\\\\1 & 1 \end{bmatrix}$ $\endgroup$– Federico PoloniCommented Jul 14, 2011 at 13:12
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
3
Write $\Sigma$ as $T^2$, for positive definite $T$. Set $Y = U T$.
So the eigenvalues of $X$ are the squares of the singular values of $Y$, and what you want to compute are the singular values of $DY$.
There is no formula which gives the singular values of $DY$ in terms of those of $Y$ and $D$. However, there is a famous set of inequalities relating the three sets of singular values, called the Horn inequalities. See Bhatia's article Linear Algebra to Quantum Cohomology, particularly Section 11, for a gentle introduction.
answered Jul 14, 2011 at 12:53
-
$\begingroup$ Thanks. Yes I came across Horn's stuff. So is this related because if you exponentiate the matrices it is addition of exponents as in the paper? $\endgroup$ Commented Jul 14, 2011 at 14:08
-
$\begingroup$ No and yes. It is not true that $e^{A} e^{B} = e^{A+B}$ so, if $A+B=C$, it need not be true that the eigenvalues of $e^A e^B$ are the exponentials of the eigenvalues of $e^C$. However, it is true that the set of all possible singular values of $e^A e^B$ is the exponential of the set of all possible eigenvalues for $A+B$. This is a theorem of Klyachko ams.org/mathscinet-getitem?mr=1799623 and it is discussed in section 11 of the refernce I give above. $\endgroup$ Commented Jul 14, 2011 at 17:25
-
$\begingroup$ Excellent, thanks that is very helpful! $\endgroup$ Commented Jul 15, 2011 at 12:59