1. Home
2. Questions
3. Tags
5. Users
6. Unanswered
Teams

Ask questions, find answers and collaborate at work with Stack Overflow for Teams.
Try Teams for free Explore Teams
Teams
Ask questions, find answers and collaborate at work with Stack Overflow for Teams. Explore Teams

Return to Answer

LDA Is a generalised eigenvalue problem, PCA is a regular eigenvalue problem

Source Link

edited Jul 10, 2018 at 11:37

865
5
14

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 generalised 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.

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 generalised 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.

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.

centering latex

Source Link

edited Jul 8, 2018 at 22:26

865
5
14

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\begin{equation} J = \max_{\mathbf{w}} \mathbf{w}^T \mathbf{S_B} \mathbf{w}, \end{equation} subject to the constraint $ \mathbf{w}^{T} \mathbf{S_W} \mathbf{w} = 1$.\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,

$ L = \mathbf{w}^T \mathbf{S_B} \mathbf{w} + \lambda(1 - \mathbf{w}^{T} \mathbf{S_W} \mathbf{w}). $\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,

$ \frac{\partial L}{\partial \mathbf{w}} = \mathbf{S_b} \mathbf{w} - \lambda \mathbf{S_w} \mathbf{w}. $\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,

$ \mathbf{S_b} \mathbf{w} = \lambda \mathbf{S_w} \mathbf{w} $.\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 $ \mathbf{A} \mathbf{w} = \lambda \mathbf{w} $.

\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 generalised 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.

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 generalised 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.

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 generalised 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.

Source Link

created Jul 8, 2018 at 22:20

865
5
14

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 generalised 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.