2
$\begingroup$

Suppose we have a n-by-n symmetric matrix K which can be factorized in a way, K = H * L * H', where L is a m-by-m diagonal matrix and H is a n-by-m matrix. In addition, let's assume n <= m.

Can we compute the eigen-decomposition of K faster by taking the advantage of this factorization?

$\endgroup$
2
  • $\begingroup$ For $n$ sufficiently less than $m$, the answer is obviously yes. For instance, take $n=1$, then $L$ is a scalar and the eigenvalue decomposition of $K$ consists of one $LH\cdot H$ eigenvalue and the rest $0$. However given the 2 answers it looks like for $n$ close to $m$ the answer is no. $\endgroup$
    – Will Sawin
    Dec 7, 2011 at 6:46
  • $\begingroup$ K is $1\times 1$, so this is not any faster than "usual". $\endgroup$ Dec 7, 2011 at 10:08

2 Answers 2

1
$\begingroup$

A completely different answer:

Given $n$-by-$n$ $K$ we can easily cook an $H$ such that $K=H*H'$ (so your $L=I$).

Let $m=n+1$-choose-$2$, associate the columns of $H$ with singletons and pairs of the original rows.

Populate a row $r$ of $H$ so that, in particular, $r$ has a 0 in any column not associated to singleton $\{r\}$ or a pair containing $r$.

Then pick values for the other entries of $H$, first to get the right off-diagonal entries of $K$ (the doubleton columns), and lastly to get the right diagonal entries (the singleton columns).

Since $H$ comes so cheap giving $K$, receiving such an $H$ tied-up-with-string can't genuinely simplify the decomposition of $K$.

$\endgroup$
1
$\begingroup$

If yes in general, then yes for $L=I$, the identity. And also yes for symmetric $n$-by-$n$ $H$ with $H^2=K$ and the same eigenvectors as $K$. It seems to me that if finding the eigenvectors of a pair $(H,H^2)$ turned out easier than finding the eigenvectors of $H^2=K$, then $H$ would have to enjoy some special structure that a generic $K$ doesn't enjoy--- because one easily completes any given $H$ to a pair $(H,H^2)$. Thus having $K$ {\em given} doesn't help and the problem turns out as hard as finding eigenvectors of $H$. But nothing generally distinguishes operators that happen to turn out equal to the square-root of given generic operators (with 1-dim eigenspaces and distinct eigenvalues).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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