28
$\begingroup$

What are the multidimensional versions of the median and what are their pros and cons? I confess this doesn't have a single answer, but I think it is a useful question to ask and will be a benefit to others as well.

How stable it is (i.e. how many samples one needs to get a reasonable estimate of it) is one potential, but not necessary, pro and con issue, i.e. if you know that the number of samples necessary grows exponentially with each increase in dimension making it useful in 10 dimensions but effectively useless in 200 dimensions, that would be useful to know. (I would kind of expect all of them have that, really, because there is so much "freedom" in 200 dimensions it just takes a bazillion points to nail the basic middle of a distribution down along that many directions).

Note: I found this question after accepting an answer for this. I hadn't seen it before because I didn't realize there was both a multivariate-analysis and a multivariable tag. I am not sure why geometric median was an unpopular answer there (1 vote and near the bottom) but a popular answer here.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
28
$\begingroup$

The Geometric Median is a generalization of the median to higher dimensions.

One of the properties of the median is that it is a point with minimal distance to all other points in the set, and GM generalizes this notion (using Euclidean/L2 distance).

Regarding robustness, the Wikipedia article mentions that: "The geometric median has a breakdown point of 0.5. That is, up to half of the sample data may be arbitrarily corrupted, and the median of the samples will still provide a robust estimator for the location of the uncorrupted data."

Next, note that in one dimension, minimizing L1 and L2 distances is the same, but in higher dimensions it is different. So, different norms will result in different generalizations. This paper, to the best of my understanding, suggests that the L1 distance generalization, which they simply call the "Minimum Sum of Distances" estimator, is also robust.

So it seems that there are at least two useful generalizations: L1 (MSoD) and L2 (GM).

For some additional perspective, note that one could also consider minimizing the square of the distances. This is in fact the arithmetic mean.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ In one dimension minimizing L1 and L2 do not give the same result? The L1 minimum of the set [4, 7, 15] is 7. The L2 minimum is 8.666... $\endgroup$
    – Ymareth
    Jun 27, 2014 at 7:32
  • 1
    $\begingroup$ Sorry, I am still confused (it is a Friday). Do you mean minimization of the distances of the points given from some hypothetical central point or something different? I agree with your value above but I don't see how it gives me the L1 minimum point which is 7? $\endgroup$
    – Ymareth
    Jun 27, 2014 at 14:27
  • $\begingroup$ @Ymareth Please ignore my previous comment. As I wrote, the median can be defined as the point with the minimal distance to all other points in the set. In other words the median is $y$ such that the sum of $||y-x_i||$ is minimal. This is why the norm won't matter in one dimension. $\endgroup$
    – Bitwise
    Jun 27, 2014 at 16:16
  • 2
    $\begingroup$ Wonderful overview of alternative formulations of the multivariate median: cgm.cs.mcgill.ca/~athens/Geometric-Estimators/intro.html $\endgroup$
    – Aditya
    Dec 26, 2017 at 13:33
  • $\begingroup$ "median is that it is a point with minimal distance to all other points in the set" - if so, then is it possible to make some sort of force field that brings you to the median no matter where is your starting point? I just wonder if it can be calculated this way, because if we can use an approximation and check only the close points by counting the actual force, then it might be a faster algorithm than the other ones that calculate with every single point. But maybe it is a silly idea. $\endgroup$
    – inf3rno
    Mar 18, 2021 at 3:40

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