Finding optimal subspace for Linear Discriminant Analysis - Elements of Statistical Learning 4.3.3

Question

Linear Discriminant Analysis (LDA) possibly operates a dimension reduction. Section 4.3.3 in Elements of Statistical Learning explicits this notion as well as a method for computing the "optimal subspace for LDA".

https://web.stanford.edu/~hastie/Papers/ESLII.pdf

Assuming $K$ classes, for a new observation $x$ LDA computes $\min_{k}{\|(\hat{\mu}_{k}^{*}-x^{*})\|^{2}}$ where $x^{*}$ and $\hat{\mu}_{k}^{*}$ are transformation of input $x$ and centroid $\hat{\mu}_{k}$ of class $k$ in a ad-hoc basis. In other terms we look for $k$ minimizing the distance of input data to the closest centroid (see more details here).

The $k$ centroids lie in an affine subspace of dimension at most $K-1$. (This is geometry, for $K=2$ we can say that two points uniquely define a line, which is of dimension $K-1=2-1=1$.) We might project $X^{*}$ onto this centroid-spanning subspace $H_{K-1}$ and compare distances there. For $p$-dimensional inputs, if $p$ is much larger than $K$ this will mean considerable drop in dimension.

Further we might pick a subspace $H_{L}\subseteq{H_{K-1}}$ of dimension $L<K-1$ which is optimal in some sense.

Fisher defined optimal to mean that the projected centroids were spread out as much as possible in terms of variance.

Then Elements of Statiscal Learning explicits the following method for finding the optimal subspace

• compute the $K \times p$ matrix of class centroids $M$ and the common covariance matrix $W$ (for within-class covariance);

• compute $M^{∗} = MW^{−1/2}$ using the eigen-decomposition of $W$;

• compute $B^{∗}$, the covariance matrix of $M^{∗}$ ($B$ for between-class covariance), and its eigen-decomposition $B^{∗} = V^{∗}DBV^{∗T}$.

The columns $v_{l}^{∗}$ of $V^{∗}$ in sequence from first to last define the coordinates of the optimal subspaces.

What is the rationale behind this method, and how is it providing the optimal subspace for LDA as per Fisher's definition of optimality ? More precisely :

• Why are $W$ the within-class and $B^{*}$ between-class covariance matrices ?

• Why do the columns $v_{l}^{*}$of $V^{*}$ define the coordinate of the optimal subspaces ?

• How do we derive the discriminant variables ?

Answer 1

Within-class, between-class covariance matrices

• Assuming common covariance matrix $\hat{\Sigma}=\hat{\Sigma}_{k}$ for all classes $k$ we write

$\hat{\Sigma}=\sum_{k=1}^{K}\sum_{g_{i}=k}{(x_{i}-\hat{\mu}_{k})(x_{i}-\hat{\mu}_{k})^{T}/(N-K)}$

where the centroid $\hat{\mu}_{k}$ is a $p$-vector estimated by $\hat{\mu}_{k}=\sum_{g_{i}=k}x_{i}/N_{k}$ and $N_{k}$ the number of elements of $X$ (the number of observations) in class $k$.

$\hat{\Sigma}$ measures the dispersion of observations around the mean of the class they belong to. We call $\hat{\Sigma}$ the within-class covariance. We denote $\hat{\Sigma}=W$.

• $M$ is the $K \times p$ matrix of centroids $\hat{\mu}_{k}$ so that its covariance matrix is given by

$\sum_{k=1}^{K}(\hat{\mu}_{k}-\bar{\mu})(\hat{\mu}_{k}-\bar{\mu})^{T}/K$

with $\bar{\mu}$ the mean of centroids $\hat{\mu}_{K}$ with $k=1..K$. It measures the dispersion of the centroids around the mean of all centroids and we call it the between-class covariance. We denote $E[M^{T}M]=B$.

• We transform $M$ into $M^{*}=MW^{-1/2}$, which operates a some basis change ( close to a whitening or sphering transformation ). I explain in the next section the rationale behind the choice for this basis. $M^{*}$ has a covariance matrix $B^{*}$.

Optimal subspace

Fisher's approach to LDA maximizes the criterion

$J(w)=w^{T}Bw / w^{T}Ww$.

We minimize the within-class covariance and maximize the between-class covariance.

$J(w)$ is invariant w.r.t. rescaling of $w \leftarrow \alpha w$, so that we can choose $\alpha$ as to have a unit denominator $w^{T}Ww=1$ ( since it is a scalar ). Thus we can turn the optimization problem into solving

$\max_{w} \frac{1}{2} w^{T}Bw$ s. t. $w^{T}Ww=1$.

Which we can rewrite after the convenient basis change $w^{*} \leftarrow W^{1/2}w$ :

$\min_{w} -\frac{1}{2}(w^{*})^{T}B^{*}w^{*}$ s. t. $(w^{*})^{T}w^{*}=1$.

The Lagrangien for this problem writes

$L = -\frac{1}{2}(w^{*})^{T}B^{*}w^{*} + \frac{1}{2}\lambda[(w^{*})^{T}w^{*}-1]$

and the Karush-Kuhn-Tucker conditions give

$B^{*}w^{*}=\lambda w^{*}$.

We see here that the basis change we operated enable to write KKT conditions for our optimization problem as an eigendecomposition. We can then write $B^{*}=V^{*}D_{B}(V^{*})^{T}$ where the columns $v_{l}^{*}$ of $V^{*}$ are the eigenvectors of $B^{*}$ and the diagonal values of $D_{B}$ its eigenvalues.

From the objective function $J(w)$ we see that the directions we look for correspond to the largest eigenvalues. Indeed under KKT conditions we have

$J(w^{*})=-\frac{1}{2}(w^{*})^{T}B^{*}w^{*}=-\frac{1}{2}(w^{*})^{T}\lambda w^{*}=-\lambda/2$

since $(w^{*})^{T}w^{*}=1$.

Finally, back to the original basis, discriminant variables are defined as $Z_{l}=v_{l}^{T}X$ with $v_{l}=W^{-1/2}v_{l}^{*}$ for $l=1..L$ corresponding to the $L$ eigenvectors $v^{*}_{l}$ with largest eigenvalue in the decomposition of the transformed between-class matrix $B^{*}$.

More information here.