# Formulation and computation of “the” unique median of an even-sized list

Consider an even-sized set of numbers $X = \{x_k\}$, such as $X = \{1, 2, 7, 10\}$.
The median $m$ is defined as:

$$m = \mathrm{arg \min_x} \sum_k \lvert x_k - x\rvert^1$$

Any $m \in [2, 7]$ is a minimizer of this function, and is therefore "a" median of this list.
Now, it is common practice to take the average of 2 and 7 and call it "the" median.

But that's lame, and I think I have invented (?) a more logical way to find a unique median $m^*$:

$$m^* = \lim_{\epsilon \to 0^+} \mathrm{arg \min_x} \sum_k \left\lvert x_k - x\right\rvert^{1+\epsilon}$$

Diferentiation to find the minimum only gets us so far:

$$\sum_k \mathrm{sgn}{\left(x_k - m^*\right)}\left\lvert x_k - m^*\right\rvert^{\epsilon} = 0$$ This expression can be solved numerically for smaller and smaller $\epsilon$ to give $m^* \approx 4.85$ in this example, and I suspect the "correct" median is in fact $m^* = 34/7$, but I don't know how to prove it.

I have 3 questions:

1. First of all, is this a well-known and/or useful approach? Does it have a name?
I came up with the new formulation myself, but I've never seen it used anywhere.

2. Is there some way to directly find the exact value of $m^*$, without numerical optimization?
If not, is there a better/faster approach than brute-force numerical optimization techniques?

3. Is this a (convex?) optimization problem, and if not, can it be reformulated as one?
The trouble here is that I can't find any objective function that has a unique minimum at $m^*$.
The best I can do is to find a generalized function (i.e., the limit of another function), but when I do that, I don't think the problem is a convex optimization problem anymore.
Is there another way to pose the problem that conforms better to existing optimization frameworks?

-
I am confused. If $m^*$ is the minimizer of a function over the elements $x\in X$, then how could $m^*=4.85\notin X$? – NotNotLogical Jun 26 '14 at 20:36
@NotNotLogical: Where did you get the idea that we must have $x \in X$? – Mehrdad Jun 26 '14 at 20:39
Ah, I was misreading. I think I now understand. – NotNotLogical Jun 26 '14 at 20:39
What's the problem with non-uniqueness here? – Peter Sheldrick Jun 26 '14 at 21:48
@PeterSheldrick: Huh? The problem is the very fact that it's not unique, even though there's a perfectly sensible definition that I demonstrated gives a unique answer. It doesn't make sense to say 2 is a median of that set, nor does it make sense to say 7 is, because neither is in the "center" of the data, even though they all minimize the typical objective. Hence it makes sense to look for a better number and thus a better objective. – Mehrdad Jun 26 '14 at 21:52

If the values are sorted $x_1 \le x_2 \ldots \le x_n$, then the value $m^*$ is the unique solution on the interval $[x_{n/2},x_{n/2+1}]$ to the following equation:

$$(m^* - x_1)(m^*-x_2)\ldots(m^*-x_{n/2})=(x_{n/2+1}-m^*)(x_{n/2+2}-m^*)\ldots(x_{n}-m^*).$$

When $n=2$, it's just the mean, and when $n=4$, $m^* = (x_3x_4-x_1x_2)/(x_3+x_4-x_1-x_2)$, which in your example is $(7\cdot 10-1\cdot2)/(7+10-1-2)=34/7$. I don't see any simple way to solve the equation in closed form for higher $n$, other than standard techniques for finding roots of polynomials.

To prove that the above equation defines $m^*$, you just need to go few steps further in the manipulation of the derivative. That is $m^* = \lim_{\epsilon\rightarrow 0^+} m_\epsilon$, where $m_\epsilon$ is the solution to:

$$\sum_{k=1}^n \mathrm{sgn}{\left(x_k - m_\epsilon\right)}\left\lvert x_k - m_\epsilon\right\rvert^{\epsilon} = 0$$

For small $\epsilon$, we should have $x_{n/2}\le m_\epsilon \le x_{n/2+1}$, so this becomes:

$$-\sum_{k=1}^{n/2} (m_\epsilon-x_k)^{\epsilon} + \sum_{k=n/2+1}^{n} (x_k-m_\epsilon)^{\epsilon}=0$$

Expanding to first order in $\epsilon$ gives: $$-\sum_{k=1}^{n/2} (1+\epsilon \log(m_\epsilon-x_k)) + \sum_{k=n/2+1}^{n} (1+\epsilon\log(x_k-m_\epsilon))=O(\epsilon^2)$$

The constant terms cancel, and dividing by $\epsilon$ gives: $$-\sum_{k=1}^{n/2} \log(m_\epsilon-x_k) + \sum_{k=n/2+1}^{n} \log(x_k-m_\epsilon)=O(\epsilon)$$

Then by taking the limit as $\epsilon \rightarrow 0^+$, we get: $$-\sum_{k=1}^{n/2} \log(m^*-x_k) + \sum_{k=n/2+1}^{n} \log(x_k-m^*)=0$$ Which is equivalent to the stated condition.

There are different ways to approximate the 1-norm with a differentiable function, and each approximation will give a different unique "median". I don't know of any reason to prefer any one approximation over another other than convenience.

-
+1 Holy cow, this looks exactly like the kind of answer I was hoping for! So you used approximated $m^* - x_k$ to first-order to be equal to its linearization $1 + \epsilon \log(m^* - x_k)$, because it's equal in the infinitesimal case? It seems so obvious in hindsight but it's very clever, I wouldn't have thought of it for quite a long time! Thanks so much, I learned something new today from your answer. :) – Mehrdad Jun 28 '14 at 0:30
Glad to help. I rewrote the argument to be more rigorous. Hopefully it's clearer now. – p.s. Jun 28 '14 at 1:18
Indeed, very nice! Well done. – Michael Grant Jun 28 '14 at 3:36
I'll bet that this is very amenable to a simple numerical search (Newton and/or bisection) with the midpoint as an initial condition. – Michael Grant Jun 28 '14 at 3:39
It also makes me wonder why first-order approximations are so special. A second-order approximation would seem correct but unhelpful, whereas a zeroth-order approximation would tell us nothing. So what's so special about first-order that gives us the answer we want exactly in the limiting case? Maybe I should ask that as a question... – Mehrdad Jun 28 '14 at 11:54

Unfortunately, this approach is not compatible with convex optimization in practice.

The reason is that in an optimization context, a convex function and its epigraph are assumed interchangeable. That is to say: consider the following two problems: $$\begin{array}{ll} \text{minimize} & f(x) \end{array}$$ $$\begin{array}{ll} \text{minimize} & y \\ \text{subject to} & f(x) \leq y \end{array}$$ These problems are equivalent if $f$ is convex: that is, given the solution to one, the solution to the other is evident, and vice-versa. Of course, the second one has an associated dual variable while the first one does not, but that doesn't change the equivalence.

Now let's consider your function for $f$, set in the second form above: $$\begin{array}{ll} \text{minimize} & y \\ \text{subject to} & \lim_{\epsilon\rightarrow 0^+} \sum_k | x_k - x |^{1+\epsilon} \leq y \end{array}$$ This is, in all practical respects, equivalent to $$\begin{array}{ll} \text{minimize} & y \\ \text{subject to} & \sum_k | x_k - x | \leq y \end{array}$$ which is of course what you'd get with the standard median function. Any practical system for optimization is really not going to be able to differentiate between the two forms. You could, of course, fix $\epsilon$ to be small and nonzero, but then you've destroyed equivalence, and of course made the leap from a linear problem to a nonlinear one.

Conceptually, what is happening here is that you are preferring a particular element of the arg min set over the rest. But establishing preferences among feasible points is precisely what the purpose of an objective function is. You need to find a way to integrate your preferences more directly into your objective or constraints. For instance, if you are determine to preserve the numerical results induced by the $|\cdot|^{1+\epsilon}$ approach---in particular, if it is important that $34/7$ be the correct answer in this example---then you will not be able to use this median function in convex optimization.

-
Thanks for the response, but I feel it's begging my own question when you say "You need to find a way to integrate your preferences more directly into your objective or constraints."... the entire point of my question was to figure out how I was supposed to do that, because as I had already mentioned, I already realized this was unlikely to work with standard (convex) optimization. Your answer just basically summarized the problem I was facing but didn't help me get anywhere. – Mehrdad Jun 26 '14 at 21:06
I am certainly not claiming to have answered every bullet point. But you did ask if this could be formulated as a (convex?) optimization problem, and I answered it. – Michael Grant Jun 27 '14 at 4:46
Besides: your definition of median is non-standard. You well know that the standard median is unique (4.5). Even if we set aside the midpoint portion of the standard statistical definition, your optimization-based definition includes two numbers (2, 7) that do not satisfy even the fundamental criteria of a median. Your definition is already a convenience, then. Certainly you are not the only one to employ this convenience in practice, but the fact remains. – Michael Grant Jun 27 '14 at 5:08
I did not ask if this could be formulated as a convex optimization problem, I asked if it was a (perhaps convex) optimization problem, and if not, whether it could be re-formulated as such a problem. All you did was tell me, "You need to find a way to integrate your preferences more directly into your objective or constraints". In other words, you just repeated back at me the obvious fact that I need to reformulate it as a convex optimization problem, without helping me actually get anywhere. – Mehrdad Jun 27 '14 at 5:37
I see no reason to accept my answer. It only addresses a part of your question. Nevertheless I will incorporate your edit... – Michael Grant Jun 27 '14 at 22:59