1
$\begingroup$

I read that in Metric learning the metric A is supposed to PSD due to the non-negativity constraint on the distance.

My question is how does A being a PSD (positive semi-definite) ensures that the distance(Mahalanobis) will be non-negative?

$\endgroup$
3
$\begingroup$

I'm assuming you mean the following distance: $$ d^2(x, y) = (x - y)^T A (x - y) .$$ Say $A$ is $n \times n$.

Recall that one definition of a positive definite matrix is that it's a symmetric matrix such that for any nonzero vector $u \in \mathbb R^n$, $u^T A u > 0$. Now, for $d$ to be a distance metric we require $d(x, y) > 0$ for any $x \ne y$. In that case, $x - y \ne 0$, and since $A$ is positive definite, $d(x, y) = \sqrt{(x - y)^T A (x - y)} > 0$.

If you prefer the definition that all eigenvalues are positive, we can prove that this property also holds from that: letting $v_i$ be the $i$th eigenvector and $\lambda_i$ its corresponding eigenvalue, we can write $u = \sum_{i=1}^n \alpha_i v_i$ since the $v_i$ are an orthonormal basis, so that \begin{align} u^T (A u) &= \left( \sum_{i=1}^n \alpha_i v_i \right)^T \left( \sum_{i=1}^n \alpha_i A v_i \right) \\&= \left( \sum_{i=1}^n \alpha_i v_i \right)^T \left( \sum_{i=1}^n \alpha_i \lambda_i v_i \right) \\&= \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j \lambda_i v_i^T v_j \\&= \sum_{i=1}^n \alpha_i^2 \lambda_i > 0 \end{align} since $v_i^T v_j = \begin{cases} 1 & i = j \\ 0 & i \ne j \end{cases}$, $\lambda_i > 0$, and at least one $\alpha_i \ne 0$ since $u \ne 0$.

The other requirements are also always satisfied. The only one that's tricky is the triangle inequality, but note that if $A$ is positive semidefinite (including if it's positive definite), there is some $R$ such that $A = R^T R$. But then $(x - y)^T R^T R (x - y) = (R x - R y)^T (R x - R y)$, so $d$ is the Euclidean distance between the points $R x$ and $R y$ – thus the triangle inequality holds.

This also gives some insight on the difference between psd and pd matrices $A$. If $A$ is pd, then any valid $R$ above is of full rank, and the points $R x$ are in an $n$ dimensional space; $d$, which is the Euclidean metric in that space, is thus a valid metric. If $A$ is psd with $m < n$ nonzero eigenvalues, then $R$ is of rank $m$, and so necessarily some distinct points in $\mathbb R^n$ are mapped to the same point in the $m$-dimensional range of $R$: there are some $x$ and $y$ such that $R x = R y$. But then $d(x, y) = 0$, making it not a valid metric. All the other properties hold, though, so that $d$ is then a pseudometric.

$\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.