4
$\begingroup$

In the derivation for Fisher's linear discriminant (the 2 class problem in particular), I notice that the between-class scatter matrix $S_B$ is said to have rank of at most 1. What is the significance of this fact to LDA process. Does this fact have an effect on the eigenvectors/values obtained from the process?

In other wards, how does the rank of $S_B$ affect the eigen vectors obtained from the product $S^{-1}_WS_B$. In general, if I multiply two matrices together, how does the rank of one matrix affect the eigenvectors of the product matrix?

$\endgroup$
1
  • $\begingroup$ this limit the number of eigenvectors with non zero eigenvalues of $S_B$ to 1 and as the FLD need to maximize $W^TS_BW$ it need to choose its eigenvectors with largest eigenvalues and a zero eigenvalue is not a choice. $\endgroup$ Sep 29, 2015 at 21:35

2 Answers 2

5
$\begingroup$

The rank of between-class scatter matrix $S_B$ for the whole data set is at most $c-1$. ($c$ is the number of classes.) The individual between-class scatter matrix $S_{Bi}$ for one class is at most $1$. The former matrix is the weighted sum of the latter.

Since $rank(AB)\le{min(rank(A), rank(B))}$, you have $rank(S^{-1}_WS_B)\le{rank(S_B)}\le{c-1}$

Rank equals the # of non-zero eigenvalues of a matrix. That means $S^{-1}_WS_B$ has at most $c-1$ non-zero eigenvalues (and corresponding eigenvectors). In order words, the rank of $S^{-1}_WS_B$ is the max # of linear discriminants you can get. This answers your first question.

The theorem $rank(AB)\le{min(rank(A), rank(B))}$ answers your second question.

$\endgroup$
1
  • $\begingroup$ if we have n samples in a class and d variables, when do we have rank problems with LDA ? Is that when n < d ? $\endgroup$
    – seralouk
    Apr 5, 2021 at 14:33
3
$\begingroup$

We know that rank(AB)<=min{rank(A),rank(B)}. Therefor, the rank of (Sw_inv)(Sb), which is the number of non-zero eigenvalues, is at most C-1 (C is the number of classes). Thus, in LDA we can reduce the dimensionality to at most C-1.

$\endgroup$

Your Answer

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

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