3
$\begingroup$

Let $X\in\mathbb{R}^{n\times p}$ denote a matrix with $p$ linearly-independent columns, and let $L\in\mathbb{R}^{n\times n}$ denote a symmetric matrix. Furthermore, let $D\in\mathbb{R}^{n\times n}$ denote a diagonal matrix with positive-entries.

Now suppose that we are interested in computing solutions to the symmetric generalized-definite eigenproblem,

$$ A v = \lambda B v, $$

where the symmetric matrices $A$ and $B$ (where $B$ is also positive-definite) are implicitly given by the matrices $X$, $L$, and $D$ above, where $A = X^T L X$, and $B = X^T D X$.

I ran into a paper which claimed that we may solve an equivalent standard eigenvalue problem involving a modification of $X$. In particular, if we orthogonalize $X$ with respect to $D$, say $\tilde X^T D \tilde X = I$, then eigenpairs of

$$ \tilde X^T L \tilde X u = \lambda u $$

are also eigenpairs for the original generalized eigenproblem. How can we show this to be true?

$\endgroup$
  • $\begingroup$ Could you clarify what your assumptions on $A$ and $B$ are? For instance, is $B$ symmetric/Hermitian and positive-definite? $\endgroup$ – Jack Poulson Oct 3 '12 at 20:00
  • $\begingroup$ @JackPoulson Edited: $A$ is symmetric, and $B$ is positive definite. However, I'm interested in the specific problem: $A=X^TLX$ and $B=X^TDX$ $\endgroup$ – usero Oct 3 '12 at 20:18
  • $\begingroup$ I am still not sure what you're getting at with your notation, would you mind providing a citation rather than saying "found in the literature"? Have you looked into the Cholesky-Wilkinson algorithm? It also reduces a problem of your form to a standard eigenvalue problem (though it should not be used if B is ill-conditioned). $\endgroup$ – Jack Poulson Oct 3 '12 at 23:23
  • 1
    $\begingroup$ No citation still? Part of what doesn't make sense is that your (1) equation is $p \times p$, and your original $Av=\lambda Bv$ equation is $n \times n$. It would really help clear things up if you said how $X$, $L$, and $D$ relate to $A$ and $B$. $\endgroup$ – Jack Poulson Oct 4 '12 at 14:27
  • 4
    $\begingroup$ I hate to sound like a broken record, but, no citation? $\endgroup$ – Jack Poulson Oct 4 '12 at 16:58
5
$\begingroup$

Let $X=\tilde X Z$, where $\tilde X^T D \tilde X=I$. Then we may rewrite

$$ (X^T L X)v = \lambda (X^T D X) v $$

as

$$ (Z^T \tilde X^T L \tilde X Z) v = \lambda (Z^T Z)v. $$

Now, put $u=Z v$, and premultiply both sides of the previous equation by $Z^{-T}$ to find

$$ \tilde X^T L \tilde X u = \lambda u. $$

It is worth noting that, contrary to your last sentence, the $u$ and $v$ are not the same, but are related through the equation $u=Z v$. Thus, after solving the standard eigenvalue problem with $\tilde X^T L \tilde X$, linear systems will need to be solved with $Z$ in order to find the original eigenvectors.

It is also important to notice that the fact that $D$ is positive is crucial to the ability to orthonormalize $X$ with respect to $D$. Consider the case where $D=-I$. Then requiring that $\tilde X^T D \tilde X = I$ is equivalent to requiring that $\tilde X^T \tilde X = -I$, which is not possible for real $\tilde X$ (nor in the complex case, when we replace transposes with Hermitian-transposes). When $D$ is positive, we may define

$$ Z = \sqrt{X^T D X}, $$

which will exist because $X^T D X$ will be positive-definite.

$\endgroup$
  • $\begingroup$ Thanks. Now it is clear why I do not want to point so publicly to mistakes of some works. $\endgroup$ – usero Oct 4 '12 at 18:05
  • 1
    $\begingroup$ @usero No, it really is not "clear". If a paper is erroneous, it is much better if that is documented somewhere. If the paper is correct, it would greatly clarify the question. Successive paraphrasing of even simple statements has a tendency to change them, so even if you are happy with evaluating the paper based on Jack's answer here, it would still help the community if you included a citation. $\endgroup$ – Jed Brown Oct 4 '12 at 19:07
  • 1
    $\begingroup$ @usero Jack's answer is great, but it would have been very simple to show that the claim is false by counterexample. (Simple exercise left to you.) Adding a citation would have greatly simplified his guess-work and editing of your post. $\endgroup$ – Stefano M Oct 4 '12 at 21:58
  • $\begingroup$ The same answer, slightly different wording, is here math.stackexchange.com/a/206604/43193 Note that the same constraint on $D$ positive. $\endgroup$ – adam W Oct 21 '12 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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