Modes, Medians and Means: A Unifying Perspective (2013)

What is the "median" or "mean" of a set of points located on the surface of a sphere, or a torus, or some more complicated manifold (which may only be defined implicitly by a distance function)? If you try to start from the one-dimensional definition it's not really clear. You can define such concepts, however, by minimizing the corresponding norms. If you minimize the sum of L1 norms then you get something like a median. If you minimize the sum of L2 norms then you get something like a mean. Once you have something like a mean you can also define something like a variance.

Wikipedia has a short article about the concept [1]. It really deserves more treatment, as it's a central (no pun in intended) idea in topological data analysis [2].

[1] https://en.wikipedia.org/wiki/Fr%C3%A9chet_mean

[2] https://en.wikipedia.org/wiki/Topological_data_analysis

1. The geometric mean is the minimizer of:

L(x) = Σ [ log(x_i) - log(x) ]²

2. The so-called Jaccard median is the minimizer of:

L(x) = Σ [ 1-J(x_i, x) ]

where J is the Jaccard overlap score (aka, IoU = Intersection over Union). The second is interesting because the Jaccard score is often used to describe how close two segmentations are in image processing. The Jaccard median can be used to consolidate multiple segmentations of the same object in such a way that is best under the Jaccard distance.

0 = d/ds sum (x_i - s)^2 = -2 sum(x_i - s) = -2 [(sum x_i) - n * s]

Thus

n*s = sum x_i

so

s = sum x_i / n

    X ~ s + eps

   p(x_1,\dots,x_n) = C * exp(-(s-x_1)^2) * exp(-(s-x_2)^2) ... * exp(-(s-x_n)^2)

   Log(p(x_1,\dots,x_n)) = - C' * sum_i (s-x_i)^2

This means if you set s to mean(x_i), you will maximize the "log-likelyhood" of your observation.

Maybe geometric motivation helps.

Consider two vectors

X = [x2,x2,...xN],

S = [(x1 - s), (x2 - s), ... , (xN - s)]

How is finding the shortest euclidean distance between X and S related to mean?

-------------------

As above we'll have some value of s_2, and a set of points x_1 < x_2 < ... x_k < s_2 < x_{k+1} < ... < x_n. We define E_2 = \sum (x_i - s_2)^2.

Suppose we move s_2 slightly to the right, obtaining s_2 + epsilon. The first k terms of the sum will increase, while the last (n-k) terms will decrease. Calculus tells us that each term will change by -2 (x_i-s_2) epsilon + O(epsilon^2). If epsilon is small (infinitesimal) we can ignore the epsilon^2 term. As expected this quantity is negative for points to the right of s_2 and positive for points to the left of s_2. We can add these up to find the total change to be

-2 × epsilon × \sum (x_i-s_2),

dropping the higher order term.

If s_2 is too far to the left, moving it to the right will decrease E_2 as the decreases from points x_{k+1}, ... x_n will be larger than the increases from points x_1, ..., x_k. Similarly if s_2 is too far to the right, moving it to the left will decrease E_2. So where's the point where we can't gain anything by moving left or right?

If we look at our expression above,

-2 × epsilon × \sum (x_i-s_2)

as a function of s_2, it's negative when s_2 is small and positive when s_2 is large. Negative means we can do better by increasing s_2; positive means we can do better by decreasing s_2. It's just a straight line, so if it's negative on one side and positive on the other side there has to be some point where it's exactly zero. At that point we can't improve E_2 at all by moving in either direction. To find that point we simply set

-2 × epsilon × \sum (x_i-s_2) = 0

and then some simple algebra gives us

s_2 = \sum(x_i)/n

-----------------

There's also a purely algebraic way to see that E_2 is minimized at the mean, without requiring any calculus. Whether it's helpful for intuition or not I don't know.

Suppose we have some value s'_2 that we're interested in, and we think this might minimize E_2:

E'_2 = \sum(x_i - s'_2)^2

I'm going to prove to you that E'_2 is not smaller than \sum(x_i - m)^2, where m is the mean. We can write

E'_2 = \sum(x_i - m + m - s'_2)^2,

since adding and subtracting m in the middle doesn't change anything. Then split it up

E'_2 = \sum((x_i - m) + (m - s'_2))^2

and expand the square

E'_2 = \sum(x_i - m)^2 + \sum(m - s'_2)^2 + 2 × \sum[(x_i - m)(m - s'_2)]

The first term is the one that I said E'_2 was not smaller than. The second term is the sum of a bunch of [identical] squares, so it is nonnegative. The third term it turns out is zero, because we can pull the (m - s\*_2) term out of the sum and then \sum(x_i - m) is zero. So we have

E'_2 = \sum(x_i - m)^2 + {nonnegative stuff},

which proves that s'_2 is not better than m. In fact the second term is strictly positive unless s'_2 = m, so m is the unique minimizer.

* you mean a strictly convex function

0 = d/ds \sum_i | x_i - s | = \sum_i sign(x_i - s)

which is true precisely when x_i <= s for half the elements and x_i >= s for the other half (taking sign(0) = 0, sign(+x) = 1, sign(-x) = -1).

As an aside, I wonder if math is sometimes difficult to understand/explain because the language is so constrained. Obviously, careful use of words is important for translating mathematical definitions verbatim, but I think a more relaxed approach to word translations of math equations would be beneficial to everyone below second year math/statistics at university. Even if they are left with a technically incomplete/incorrect definition or intuition for a given concept.

You pick the one that treats discrepancy the way that's appropriate.

E.g., using the mode is like saying "if you're not the right answer, you're all equally bad".

Using the median is like saying "if you're not the right answer, you're as wrong as however far off you are".

Using the mean is like saying "if you're not the right answer, you're more and more wrong the further away you are, and the amount you're penalized itself gets more and more, so you're really incentivized to be closer"

Which of these is appropriate depends on the real thing you care about in whatever your numbers actually signify.