4

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?

Andy
  • 19,098
Minaj
  • 1,421
  • 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. – Karim Tarabishy Sep 29 '15 at 21:35

2 Answers2

5

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.

Xiao-Feng Li
  • 591
  • if we have n samples in a class and d variables, when do we have rank problems with LDA ? Is that when n < d ? – seralouk Apr 05 '21 at 14:33
3

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.

P. Adibi
  • 31