The Multiclass Fisher Discriminant Eigenproblem

From Separating One Direction to Several

For two classes, a direction can be assessed by comparing how far apart the projected class means are with how much projected variation occurs within the classes. With several classes, the same idea applies, but the mean differences point in multiple directions. The multiclass Fisher discriminant problem gathers those differences into a matrix and asks which directions provide the greatest between-class separation relative to within-class variation.

The result is a generalized eigenvalue problem, not ordinarily an eigenproblem for the between-class scatter matrix alone. The within-class scatter matrix supplies the metric in which directions are compared and normalized.

If \(a\in\mathbb{R}^p\) is a nonzero direction, projecting an observation onto it gives the scalar \(a^Tx_i\). The weighted sum of squared differences between projected class means is \(a^TBa\), while the sum of within-class squared deviations after projection is \(a^TWa\). Thus, when \(a^TWa>0\), Fisher’s one-direction criterion is $$ J(a)=\frac{a^TBa}{a^TWa}. $$ Multiplying \(a\) by any nonzero constant does not change \(J(a)\), so a normalization is needed to select a particular representative of a direction.

The Generalized Eigen-Equation

The single-direction problem is to maximize \(J(a)\) over nonzero \(a\) for which \(a^TWa>0\). If \(W\) is positive definite, then every nonzero direction has positive within-class scatter. The quotient is unchanged by rescaling \(a\), so we may impose \(a^TWa=1\) and maximize \(a^TBa\). A Lagrange multiplier gives $$ Ba=\lambda Wa. $$ Indeed, the gradient of \(a^TBa-\lambda(a^TWa-1)\) is \(2Ba-2\lambda Wa\), since both matrices are symmetric. Multiplying the equation by \(a^T\) shows that \(\lambda=a^TBa\) under the normalization \(a^TWa=1\). Equivalently, for any nonzero solution, its generalized eigenvalue is the quotient \(J(a)\).

This result can be derived by converting the generalized problem into an ordinary symmetric eigenproblem. A positive definite \(W\) has a symmetric positive definite square root \(W^{1/2}\) and inverse \(W^{-1/2}\). Set \(u=W^{1/2}a\), and define \(C=W^{-1/2}BW^{-1/2}\). Then $$ J(a)=\frac{u^TCu}{u^Tu}. $$ The matrix \(C\) is symmetric, so the spectral theorem gives an orthonormal eigenbasis and real eigenvalues. Expressing \(u\) in that basis shows that its quotient is a weighted average of the eigenvalues, with nonnegative weights summing to one. It cannot exceed the largest eigenvalue, and equality is attained by a corresponding eigenvector \(u\). Transforming back gives \(a=W^{-1/2}u\), which satisfies \(Ba=\lambda Wa\). This also explains why the generalized eigenvalues are real. Since \(B\) is positive semidefinite, they are nonnegative.

Choosing Several Discriminant Directions

For an \(r\)-dimensional discriminant representation, put the direction vectors in a \(p\times r\) matrix \(A\). The projected between-class scatter is \(A^TBA\), and the projected within-class scatter is \(A^TWA\). A standard joint choice fixes the within-class scatter to the identity and maximizes the total between-class scatter: $$ \text{maximize }\operatorname{tr}(A^TBA) \quad\text{subject to }A^TWA=I_r. $$ Here \(I_r\) is the \(r\times r\) identity matrix and \(\operatorname{tr}\) is the sum of diagonal entries. This optimization is defined for \(1\le r\le p\): when \(W\) is positive definite, \(r\) \(W\)-orthonormal directions can be selected in \(\mathbb{R}^p\), but more than \(p\) cannot.

To prove the theorem, form \(C=W^{-1/2}BW^{-1/2}\) and set \(Q=W^{1/2}A\). The constraint becomes \(Q^TQ=I_r\), and the objective becomes \(\operatorname{tr}(Q^TCQ)\). Let the eigenvalues of \(C\) be ordered \(\lambda_1\ge\cdots\ge\lambda_p\), with corresponding orthonormal eigenvectors in the columns of \(U\). Write \(Z=U^TQ\). Then \(Z^TZ=I_r\), and $$ \operatorname{tr}(Q^TCQ)=\sum_{i=1}^p\lambda_i d_i,\qquad d_i=\sum_{j=1}^r z_{ij}^2. $$ Each \(d_i\) lies between zero and one: it is the squared length of the projection of a unit coordinate vector onto the \(r\)-dimensional column space of \(Z\). Also \(\sum_i d_i=\operatorname{tr}(Z^TZ)=r\). Consequently, $$ \sum_{i=1}^r\lambda_i-\sum_{i=1}^p\lambda_i d_i =\sum_{i=1}^r\lambda_i(1-d_i)-\sum_{i=r+1}^p\lambda_i d_i\ge 0. $$ For the inequality, the total weights on the two sums are equal because \(\sum_{i=1}^r(1-d_i)=\sum_{i=r+1}^p d_i\). Every eigenvalue in the first sum is at least \(\lambda_r\), and every eigenvalue in the second is at most \(\lambda_r\). The bound is attained by taking the columns of \(Q\) to be eigenvectors for the \(r\) largest eigenvalues. Mapping back with \(A=W^{-1/2}Q\) gives \(A^TWA=I_r\), and its columns solve the generalized eigen-equation. This proves the stated maximum and characterization. \(\square\)

Common Pitfall and Practical Interpretation

A common mistake is to take the ordinary eigenvectors of \(B\) and assume they solve the Fisher problem. Those eigenvectors maximize between-class scatter under Euclidean normalization, not under within-class normalization. Fisher’s criterion instead compares \(a^TBa\) with \(a^TWa\); the correct equation is \(Ba=\lambda Wa\). The distinction matters when within-class variability differs across features or combines features through off-diagonal entries. The examples also show why the normalization \(A^TWA=I_r\) is substantive: it makes the chosen directions orthonormal in the within-class scatter metric, rather than merely in ordinary Euclidean distance.

The positive-definiteness assumption on \(W\) ensures that every nonzero direction has positive within-class scatter and that the whitening transformation used in the proofs exists. If \(W\) is singular, these arguments do not apply directly; the data may have directions with zero within-class scatter, and the problem needs an explicitly chosen restriction or regularization before using an ordinary generalized eigenproblem. Likewise, the dimension \(r\) in the trace theorem must satisfy \(1\le r\le p\); for \(r>p\), the constraint has no feasible \(p\times r\) matrix.

These directions summarize class-mean separation relative to within-class scatter. They are useful for constructing a lower-dimensional representation of labelled data, but the eigenvalues are separation criteria, not posterior probabilities or classification error rates. Classification still requires a decision rule and, where appropriate, class priors and misclassification costs.