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

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?

share|improve this question
    
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. –  Will Sawin Dec 7 '11 at 6:46
    
K is $1\times 1$, so this is not any faster than "usual". –  Federico Poloni Dec 7 '11 at 10:08

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

share|improve this answer

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

share|improve this answer

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.