Solve a generalized eigenvalue problem in LDA

Question

http://www.facweb.iitkgp.ernet.in/~sudeshna/courses/ML06/lda.pdf

Page 6.

I don't quite understand how that can be solved...

I have tried following general one $$det(S^{-1}_{w}S_B-JI)=0$$

But I am not sure if any further insights can be provided.

Answer 1

From your question link, I can see that you’re interested in seeing how solving the eigenvalue problem $S_w^{ -1} S_b w - Jw = 0$ shows that the vector $w = S_w^{ -1}( {\mu_1 - \mu_2 })$ maximizes $$J = \left( {\frac{{\left( {\tilde \mu_1 - \tilde \mu_2 } \right)^2 }}{{\tilde s_1^2 + \tilde s_2^2 }}} \right) = \left( {\frac{{w^T S_B w}}{{w^T S_w w}}} \right),$$ where $S_b$ and $S_w$ are $n\times n$ matrices, where $w$, $\mu_1$, and $\mu_2$ are $n$-dimensional column vectors, and $S_b = \left( {\mu_1 - \mu_2 } \right)\left( {\mu_1 - \mu_2 } \right)^T$.

We observe in this problem that $S_b$ is a rank-$1$ outer product and therefore has an $n-1$ dimensional null-space. In particular, since we can write $$S_b v = \left( {\mu_1 - \mu_2 } \right)\left( {\mu_1 - \mu_2 } \right)^T v = \left[ {\left( {\mu_1 - \mu_2 } \right)^T v} \right]\left( {\mu_1 - \mu_2 } \right)$$ it’s clear that $S_b$ annihilates all vectors orthogonal to $\left( {\mu_1 - \mu_2 } \right)$ and that if $v$ is not in the null-space of $S_b$ that the matrix-vector product $S_b v$ will be a multiple of the vector $\left( {\mu_1 - \mu_2 } \right)$. Applying these observations to the eigenvalue problem $S_w^{-1} S_b w = Jw$, we see that (1) $S_w^{-1} S_b$ has an eigenvalue of $0$ with multiplicity at least $n-1$ (corresponding eigenvectors being orthogonal to $\left( {\mu_1 - \mu_2 } \right)$) and that (2) the (at most) one non-zero eigenvalue corresponds to a vector in the direction $S_w^{ - 1} \left( {\mu_1 - \mu_2 } \right)$. Since $J$ is clearly nonnegative and satisfies the eigenvalue problem for $w=S_w^{-1} \left( {\mu_1 - \mu_2 } \right)$, this (at most) one non-zero eigenvalue for the eigenvalue problem is the desired maximal value of $J$. Therefore we've shown that a vector in the direction $w = S_w^{-1} \left( {\mu_1 - \mu_2 } \right)$ maximizes $J$.

To actually show that the eigenvalue $J$ has the prescribed form, we can proceed as follows. For shorthand, let $\mu =\mu_1 -\mu_2$. Then $w = S_w^{-1}\mu$ and

$$S_B S_W^{-1}\mu = \mu\mu^T S_W^{-1}\mu = ({\mu^T S_W^{-1} \mu})\mu$$

since $\mu^T S_W^{-1}\mu$ is just a scalar. This scalar is the eigenvalue $J$ we are seeking since it satisfies the eigenvalue problem $S_W^{ -1} S_B (S_W^{ -1}\mu) = \left( {\mu^T S_W^{-1} \mu } \right)(S_W^{-1} \mu)$. We can go on to rewrite $J$ as a ratio of quadratic forms like this:

$$J = \left( {\mu ^T S_W^{ - 1} \mu } \right) = \frac{{\left( {\mu ^T S_W^{ - T} \mu } \right)\left( {\mu ^T S_W^{ - 1} \mu } \right)}}{{\left( {\mu ^T S_W^{ - T} \mu } \right)}} = \frac{{\mu ^T S_W^{ - T} (\mu \mu ^T )S_W^{ - 1} \mu }}{{\left( {\mu ^T S_W^{ - T} S_W S_W^{ - 1} \mu } \right)}} = \frac{{w^T S_B w}}{{w^T S_W w}}.$$