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


2 Answers 2


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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – amoeba
    Jul 10, 2018 at 11:30
  • $\begingroup$ 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. $\endgroup$
    – boomkin
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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