Derivation of $S_W^{-1} S_B$ during the calculation of LDA

Question

I try to reason the computations during the search for the optimal weight vector $w$ during the calculations of LDA. Therefore I use several text books like:

1. Kuhn, M. and Johnson, K. (2013) Applied Predictive Modeling. New York: Springer. p.289
2. Hastie, T., Tibshirani R. and Friedman, J. (2008). The Elements of Statistical Learning. 2nd ed. Stanford: Springer. p.116

In the 2nd book the authors write that the $w$ which maximises $\frac{w^TS_Bw}{w^tS_Ww}$ can be found by finding the eigenvalues of the matrix $S_W^{-1}S_B$.

But why is this and how do they come to this equation $S_W^{-1}S_B$?

Answer 1

Hastie, T., Tibshirani R. and Friedman, J. (2008). The Elements of Statistical Learning. 2nd ed. Stanford: Springer. p.116, the author states that the optimisation problem of the Fisher's LDA is (Equation 4.16),

\begin{equation} J = \max_{\mathbf{w}} \mathbf{w}^T \mathbf{S_B} \mathbf{w}, \end{equation} subject to the constraint \begin{equation} \mathbf{w}^{T} \mathbf{S_W} \mathbf{w} = 1. \end{equation}

This problem can be solved using Lagrangian optimisation, by rewriting the cost function in the Lagrangian form,

\begin{equation} L = \mathbf{w}^T \mathbf{S_B} \mathbf{w} + \lambda(1 - \mathbf{w}^{T} \mathbf{S_W} \mathbf{w}). \end{equation}

Now, it is possible to take the partial derivative of this function to find maxima,

\begin{equation} \frac{\partial L}{\partial \mathbf{w}} = \mathbf{S_b} \mathbf{w} - \lambda \mathbf{S_w} \mathbf{w}. \end{equation}

Setting this zero and rearranging we obtain,

\begin{equation} \mathbf{S_b} \mathbf{w} = \lambda \mathbf{S_w} \mathbf{w} .\end{equation}

Notice, that we can rearrange this to the form of an eigenvalue problem. The equation of an eigenvalue problem is

\begin{equation} \mathbf{A} \mathbf{w} = \lambda \mathbf{w}. \end{equation}

So by inspection and rearranging we can see, that the optimisation problem can be recasted to finding the eigenvectors of the matrix $ \mathbf{S_w}^{-1} \mathbf{S_b} $.

I think further insight into this problem can be obtained by comparing it with Principal Components Analysis. If you have a solid understanding on why PCA results in a eigenvalue problem, then it becomes much more straightforward that LDA is effectively a "regularisation" of the PCA problem and thus leads to a similar solution.

Answer 2

As an addition to @bookmins answer the concept of how to get to the term $S_W^{-1}S_B$ can be looked up here and in Marsland, S. (2015). Machine Learning an Algorithmic Perspective. 2nd ed. Boca Raton: CRC Press. p.132 as well.
Additionally, here is stated, that finding the maximum of
$$\frac{\boldsymbol{w}^T S_B \boldsymbol{w}}{\boldsymbol{w}^T S_W \boldsymbol{w}}$$ is the same as maximizing the nominator while keeping the denominator constant and therewith can be denoted as kind of a constrained optimization problem with:

$\max_\limits{w}\boldsymbol{w}^TS_B\boldsymbol{w}$ with the constraint $\boldsymbol{w}^TS_W\boldsymbol{w}=K$

Bringing this constrained optimization problem into Lagrangian form gives: $$L=\boldsymbol{w}^T S_B \boldsymbol{w}-\lambda(\boldsymbol{w}^T S_W \boldsymbol{w}-K)$$ Finding the maximum of a funcion can be accomplished by calculating and setting the derivative equal to zero. $$\frac{\delta L}{\delta \boldsymbol{w}}=S_B\boldsymbol{w}-\lambda S_W\boldsymbol{w}=\boldsymbol{0}$$ or $$S_B\boldsymbol{w}=\lambda S_W \boldsymbol{w}$$
This is a generalized Eigenvalue problem and can (providing that $S_W^{-1}$ exists) be written as: $$S_W^{-1}S_B\boldsymbol{w}=\lambda\boldsymbol{w}$$ $$=$$ $$(S_W^{-1}S_B-\lambda\boldsymbol{I})\boldsymbol{w}=0$$ Solving this equation gives us the Eigenvalues ($\lambda$) and Eigenvectors ($\boldsymbol{w}$) and can be accomplished using numpy.linalg.eig(a) setting $S_W^{-1}S_B$ for a or manually by calculating $det(S_W^{-1}S_B-\lambda\boldsymbol{I})=0$, solving for $\lambda$ which gives us the Eigenvalues. Inserting these Eigenvalues ($\lambda$) into $(S_W^{-1}S_B-\lambda\boldsymbol{I})\boldsymbol{w}=0$ gives us a linear set of equations and solving these equations for $\boldsymbol{w}$ gives us the corresponding Eigenvectors.