3
$\begingroup$

I am not very up to date on my linear algebra skills and I am having some trouble understanding an explanation from the book Pattern Recognition and Machine Learning, (Bishop).

It says , consider Mahalnobis distance, $\Delta^{2}=(x-\mu)^{T}\Sigma^{-1}(x-\mu)$

Where $\Sigma$ is a real symmetric matrix ( the variance covariance matrix).

"Because $\Sigma$ is real and symmetric, its eigenvalues will be real and its eigenvectors can be chosen to form an orthonormal set, so that ..."

$u_{i}^{T}u_{j}=I_{ij}$

and $\Sigma$ can be written as

$$\Sigma= \sum_{i=1}^{D} \lambda_{i} u_{i}u_{i}^{T}$$

and $$\Sigma^{-1}=\sum_{i=1}^{D} \frac{1}{\lambda_{i}}u_{i}u_{i}^{T}$$

so $$\Delta^{2}=\sum_{i=1}^{D} \frac{y_{i}^{2}}{\lambda_{i}}$$

where $$y_{i}=u_{i}^{T}(x-\mu)$$

I am just looking to understand these steps better. I don't understand how it is achieved. I understand the basics such as real spectral theorem tells us we have a diagonlization with an orthogonal matrix, but I do not understand how they use that to calculate $\Sigma$ , $\Sigma^{-1}$ and the choice of $y_{i}$. I am more interested in the actual interpretation. The geometric and how it it can be used.

Thanks to anyone who can help.

$\endgroup$
2
$\begingroup$

First of all, the Mahalanobis distance is actually defined as $\sqrt{\Delta^2} = \sqrt{(x-\mu)^\intercal \Sigma^{-1}(x-\mu)}$. Think in analogy to the "Euclidean" distance (the "usual" distance between two points), which is the square root of the sum of squares.

The main idea behind using eigenvectors is that you're choosing a basis for $\Bbb{R}^D$ that is "better suited" for the application of the matrix $\Sigma$ and its inverse. The better basis is the basis consisting of (orthonormalized) eigenvectors of $\Sigma$.

Why is this a "better" basis, you ask? Well, several reasons:

  1. If $u_j$ is an eigenvector of $\Sigma$, we have $\Sigma u_j = \lambda_j u_j$. In other words, applying the linear transformation is really easy for eigenvectors: we just scale them.
  2. Because $\Sigma$ is positive semi-definite, we can make an orthonormal basis of eigenvectors. Orthonormal bases are particularly nice because expressing an arbitrary vector in that basis is easy. Say $y\in \Bbb{R}^D$. Then, saying $\{u_j\}$ is an orthonormal basis is equivalent to saying that

$$ y = \sum_{j=1}^D (y^\intercal u_j) u_j = \sum_{j=1}^Du_j(u_j^\intercal y) $$ Why is this identity helpful? If we apply $\Sigma$ and use the fact that $\Sigma u_j = \lambda_j u_j$, we immediately see why:

$$ \Sigma y = \sum_{j=1}^D\Sigma u_j (u_j^\intercal y)= \sum_{j=1}^D\lambda_j u_j (u_j^\intercal y) \tag{1} $$ Another way to write this is simply

$$ \Sigma = \sum_{j=1}^D\lambda_j u_ju_j^\intercal \tag{2} $$ (Apply both sides to $y$ to see why (1) and (2) are the same). Note that (2) is completely equivalent to the "spectral decomposition" of $\Sigma$, which is usually written as

$$ \Sigma = U\Lambda U^\intercal \tag{3} $$ where $U$ is the matrix of eigenvectors, which satisfies $U^\intercal U = I$, and $\Lambda$ is the diagonal matrix of eigenvalues.

  1. Not only is it easy to apply $\Sigma$ if we change basis to $\{u_j\}$, but it's also easy to apply the inverse. Suppose we want to solve the equation

$$ \Sigma x = y $$ Using the matrix expression (3), we can write this as

$$ U\Lambda U^\intercal x = y $$ Now, we know that $U^\intercal U = I$, so we can apply $U^\intercal$ to both sides of the equation:

$$ U^\intercal U\Lambda U^\intercal x = U^\intercal y $$ and so

$$ \Lambda U^\intercal x = U^\intercal y \tag{4} $$ what this equation says, by the way, is that the coefficients of $x$ in the basis $\{u_j\}$ are related to the coefficients of $y$ in the basis $\{u_j\}$ by a diagonal matrix $\Lambda$. Assuming that $\lambda_j>0$, we can solve the equation (4) easily too:

$$ U^\intercal x = \Lambda^{-1}U^\intercal y $$ The inverse of a diagonal matrix is just the diagonal matrix with $1/\lambda_j$, by the way. Finally, we can apply $U$ to both sides to get

$$ x = U\Lambda^{-1}U^\intercal y $$ Another way to write this is

$$ x = \Sigma^{-1}y = \sum_{j=1}^D \frac{1}{\lambda_j} u_j u_j^\intercal y \tag{5} $$ Or, equivalently,

$$ \Sigma^{-1} = \sum_{j=1}^D \frac{1}{\lambda_j}u_ju_j^\intercal $$ Finally, how do we use these expressions to get the Mahalanobis distance in the eigenvector basis? Well, suppose first that we want to compute $\Sigma^{-1}(x - \mu)$. We can simply apply expression (5):

$$ \Sigma^{-1}(x-\mu) = \sum_{j=1}^D\frac{1}{\lambda_j}u_ju_j^\intercal (x-\mu) =\sum_{j=1}^D\frac{u_j^\intercal (x-\mu) }{\lambda_j}u_j $$ Now, to compute $\Delta^2$, we multiply both sides by $(x-\mu)^\intercal$, use linearity of sums and symmetry of the dot product:

$$ \Delta^2 = (x-\mu)^\intercal \sum_{j=1}^D\frac{u_j^\intercal (x-\mu) }{\lambda_j}u_j = \sum_{j=1}^D\frac{u_j^\intercal (x-\mu) }{\lambda_j}(x-\mu)^\intercal u_j = \sum_{j=1}^D \frac{y_j^2}{\lambda_j} $$where $y_j = (x-\mu)^\intercal u_j$.

Geometrically, what does $y_j = (x-\mu)^\intercal u_j$ represent? Well, think of $x$ as a datapoint; subtracting the mean simply makes the origin $\mu$ instead of $0$. Then, $(x-\mu)^\intercal u_j$ is the component of the (re-centered) datapoint in the direction of the eigenvector $u_j$. This eigenvector is usually called a principal component in the statistics literature; so, $(x-\mu)^\intercal u_j$ is the "amount" of the (re-centered) datapoint in the direction of the $j$th principal component.

So why is the Mahalanobis distance a "distance"? Is there a geometric interpretation of this? Indeed - we're switching our basis to the principal component (eigenvector) basis, then simply computing a weighted euclidean distance between our data point $x$ and the mean $\mu$. The weights are the (inverse) eigenvalues $\lambda_j$. Why choose these weights? Well, smaller eigenvalues of $\Sigma$ correspond to weaker correlations; we want to normalize correlations before computing the distance.

Another good way to think about it is that we're performing a whitening transformation before computing distances: if we define

$$ z = \Sigma^{-1/2}(x-\mu) $$ Then, we have

$$ \Delta^2 = z^\intercal z $$ It's called a whitening transformation because it converts random vectors to "white noise", i.e. vectors with mean $0$ and covariance $I_{D\times D}$. This is just like the "Z score" transformation you learn in Stat 101:

$$ Z = \frac{x-\mu}{\sigma} $$

Hope that helps. Usually I would draw pictures but I don't have the time. There should be some YouTube videos out there on Mahalanobis and PCA that can help.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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