# Computations for LDA: Eigendecomposition

While reading the book Elements of Statistical Learning p. 113, the author used eigendecomposition of the covariance matrix $\hat{\Sigma}_k =\mathbf{U}_k\mathbf{D}_k\mathbf{U}_k^T$ where $\mathbf{U}_k$ is $p \times p$ orthonormal, and $\mathbf{D}_k$ a diagonal matrix of positive eigenvalues $d_{kl}$

The formula for the quadratic function is as follows:

$$\delta_k(x) = -\frac{1}{2}\log|\mathbf{\Sigma}_k|-\frac{1}{2}(x-\mu_k)^T\mathbf{\Sigma}^{-1}_k(x-\mu_k)+\log \pi_k$$

Using the idea of eigendecomposition the $\delta_k(x)$ is redefind:

1) $(x-\mu_k)^T\mathbf{\Sigma}^{-1}_k(x-\mu_k) = |\mathbf{U}_k^T(x-\mu_k)|^T\mathbf{D}_k^{-1}|\mathbf{U}_k^T(x-\mu_k)|$

2) $\log|\hat{\mathbf{\Sigma}}| = \Sigma_l\log(d_{kl})$

Apparently, the computational steps for the LDA classifier can be implemented by starting with the following step:

$Sphere$ the data with respect to the commmon covariance estimate $\hat{\Sigma}$:

$X^*\leftarrow \mathbf{D}^{-\frac{1}{2}}\mathbf{U}^TX$, where $\hat{\mathbf{\Sigma}} = \mathbf{UDU}^T$. The common covariance estimate of $X^*$ will now be the identity.

I did not understand how the author came to this step and I don't know how to read the back arrow from $\mathbf{D}^{-\frac{1}{2}}\mathbf{U}^TX$. Anybody who has an idea where I should start or how I should tackle this? What do I have to imagine when reading $X^*$?

• What is the definition of $\mu_k$ and $\pi_k$? – Marc Bogaerts Aug 31 '14 at 21:11
• $\mu_k$ is the mean of class k and $\pi_k$ the prior probability of class k. These are estimated as $\hat{\pi}_k = N_k/N$, where $N_k$ is the number of class-k observations; and $\hat{\mu}_k = \Sigma_{g_{i=k}}x_i/N_k$. – hendiadys Aug 31 '14 at 21:20
• So, mathematically, these are just some unrelated numbers? – Marc Bogaerts Aug 31 '14 at 21:42
• Yes, I guess so. $\pi_k$ is just a scalar, $\mu_k$ will be a vector of means for each variable in class k so $\mu_k = (\mu_{k1}, \mu_{k2}, ... \mu_{kp})^T$. – hendiadys Aug 31 '14 at 21:48

What you might want to begin with here is the most general form of the discriminant function that is mentioned in the text:

$$\delta_{k}(x) = log \ \mathbb{P} (G = k | X = x)$$

Under assumptions that $$X | G = k \sim \mathcal{N}(\mu_{k},\,\Sigma)$$ and $$\mathbb{P} (G = k) = \pi_{k}$$ (as introduced for linear discriminant analysis in the book) and after eliminating normalization constant from normal distribution density (because it is common for all discriminants) you obtain

$$\delta_{k} (x) = - \frac{1}{2} (x - \mu_{k})^{T} \Sigma^{-1} (x - \mu_{k}) + log \ \pi_{k}$$ by Bayes theorem obviously. From here (after plugging in $$\mu_{k}$$, $$\Sigma$$ and $$\pi_{k}$$ estimates) you can either simplify again to obtain linear discriminant functions by removing common quadratic term (and arrive at

$$\delta_{k} (x) = x^{T} \hat{\Sigma}^{-1} \hat{\mu}_{k} - \frac{1}{2} \hat{\mu}_{k}^{T} \hat{\Sigma}^{-1} \hat{\mu}_{k} + log \ \hat{\pi}_{k}$$ which is eq. (4.10) in II edition of ESL) or you can use eigenvalue decomposition of $$\hat{\Sigma}$$ just like the authors used it for $$\hat{\Sigma}_{k}$$ (which you mention in 1) in your question):

\begin{align} \delta_{k} (x) &= - \frac{1}{2} (\mathbf{U}^{T} (x - \hat{\mu}_{k}))^{T} \mathbf{D}^{-1} (\mathbf{U}^{T}(x - \hat{\mu}_{k})) + log \ \hat{\pi}_{k} \\ &= - \frac{1}{2} (\mathbf{U}^{T} (x - \hat{\mu}_{k}))^{T} \mathbf{D}^{- \frac{1}{2}} \mathbf{D}^{- \frac{1}{2}} (\mathbf{U}^{T}(x - \hat{\mu}_{k})) + log \ \hat{\pi}_{k} \\ &= - \frac{1}{2} (\mathbf{D}^{- \frac{1}{2}} \mathbf{U}^{T} (x - \hat{\mu}_{k}))^{T} (\mathbf{D}^{- \frac{1}{2}} \mathbf{U}^{T}(x - \hat{\mu}_{k})) + log \ \hat{\pi}_{k} \\ &= - \frac{1}{2} \left \Vert \mathbf{D}^{- \frac{1}{2}} \mathbf{U}^{T} (x - \hat{\mu}_{k}) \right \Vert^{2}_{2} + log \ \hat{\pi}_{k}, \end{align} where obviously $$\hat{\Sigma} = \mathbf{U D U}^{T}$$ is the eigendecomposition.

So we have an alternative form of the discriminant function. Now to my understanding that back arrow in $$X^{\ast} \leftarrow \mathbf{D}^{- \frac{1}{2}} \mathbf{U}^{T} X$$ means that the first step of this LDA implementation is to apply the sphering transform (linear map defined by $$\mathbf{D}^{- \frac{1}{2}} \mathbf{U}^{T}$$ matrix) to each observation (both in training set and to inputs at prediction time). That means we transform each row of the $$N \times p$$ data matrix $$\mathbf{X}$$ (matrix rows of which are training observations), so we obtain $$\mathbf{X}^{\ast} = \mathbf{X} \mathbf{U} \mathbf{D}^{- \frac{1}{2}}$$. Class labels of the observations do not change, so you can again consider class centroids - and it can be easily seen that the centroids in the transformed data are of form $$\mathbf{D}^{- \frac{1}{2}} \mathbf{U}^{T} \hat{\mu}_{k}$$.

And not only that, it's rather trivial to derive covariance matrix of the transformed data $$\mathbf{X}^{\ast}$$ and see that it's indeed identity matrix. Hence the name: sphering or whitening the data, because separate features are now uncorrelated and have unit variance. If the term is unfamiliar to you, you might want to start at https://en.wikipedia.org/wiki/Whitening_transformation, if you haven't already.

Having said all that we can go back to our alternative form of discriminant above and see that the first term is indeed square distance between $$k$$ class centroid in the transformed data and transformed input observation $$x$$. Hence maximizing the discriminant amounts to classifying

to the closest class centroid in the transformed space, modulo the effect of the class prior probabilities $$\pi_{k}$$.

to quote the book.