Question

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?

Answer 1

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).

Answer 2

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$.