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

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

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

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

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

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

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

$$\frac{\partial L}{\partial \mathbf{w}} = \mathbf{S_b} \mathbf{w} - \lambda \mathbf{S_w} \mathbf{w}.$$

Setting this zero and rearranging we obtain,

$$\mathbf{S_b} \mathbf{w} = \lambda \mathbf{S_w} \mathbf{w} .$$

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

$$\mathbf{A} \mathbf{w} = \lambda \mathbf{w}.$$

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.

• Good answer overall, but I am confused by the last paragraph. PCA does not result in a generalized eigenvalue problem; it results in a "standard" (non-generalized) eigenvalue problem. Jul 10, 2018 at 11:30
• I edited the answer, I didn't know that the term "generalised eigenvalue problem" had a separate meaning, but I looked up and and indeed it is misleading in this case. On top of my head, I would consider using one matrix instead of two "more general", but I guess the word "standard" is the right one here. Jul 10, 2018 at 11:44

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.