# Proxy for Mahalanobis distance when n < p? [duplicate]

I'm working on a ranking problem where I want to measure the distance between a collection of query points (as a group) and each target point in my database. Each query point is part of the set of target points. I started with the Euclidean distance and cosine similarity by using the mean vector of the query points. However, the results were not satisfactory possibly because both of these measures don't take into account the variance and covariance of the query points. I stumbled across the Mahalanobis distance which seems to be exactly what I want to try: Measuring how many standard deviations a point is away from the mean of the subsample.

The problem is that I work in a 256-dimensional space while the number of query points is usually much lower than that. Therefore, I cannot calculate the Mahalanobis distance which relies on the covariance matrix. In order to calculate it, I need more observations n than dimensions p.

1) Is this assumption correct?

The past days I've been thinking about how I could still do "better" than the Euclidean distance without having enough data to calculate the Mahalanobis distance.

I thought about switching out the covariance matrix for the diagonal matrix of variances. As long as none of the variances is zero an inverse can be calculated.

2) Does this idea have a flaw?

Since the 256-dimensional vectors are the result of PCA over all target points, I could use n points to create a covariance matrix over the first n-1 dimensions and then fill the rest of the needed 256-dim covariance matrix with the diagonal of variances from before.

3) Would that make any sense?

4) Any other ideas that might help me to measure a more meaningful distance between a point and a subsample of points?

Please note: A very similar question has been asked here but I believe my problem is still different. There, OP wanted to measure pairwise distances between points given all points. I want to measure the distance between the distribution of a subsample to all other points. I believe, the reasoning of the accepted answer does not apply to my problem since the distribution of the subsample is likely to be different.

• Commented Apr 25, 2019 at 12:41
• thank you. these two links helped me. Commented Apr 26, 2019 at 14:38