Introduction to the Median

中位数（Median）简介 苏剑林 · 2026-03-31 · Mathematics algebra statistics probability geometry

I recently revisited the concept of the median, and while it's still fresh in my mind, I thought I'd jot down the key points.

When doing outlier removal or clipping, we often need some kind of "reference point" — for instance, given a bunch of non-negative data, we might decide that anything more than 50 times the reference value counts as an outlier. So how should we choose this reference? A commonly used metric is the mean. However, the mean is easily "dragged along" by outliers, so using it as a reference might end up biased toward the outliers themselves, causing us to miss some cases. In such situations we might instead consider using the median as the reference.

Basic Properties

For a set of one-dimensional data points $x_1,x_2,\cdots,x_n$, their mean is defined as

\begin{equation}\newcommand{mean}{\mathop{\text{mean}}}\mean(x_1,x_2,\cdots,x_n) = \frac{1}{n}\sum_{i=1}^n x_i\end{equation}

Since all the data participate directly in computing the average, once a few points become extremely large, the mean will be dragged along with them, which interferes with outlier detection. more

The idea behind the median is to find the "neutral party" in the data to serve as the reference. Specifically, it seeks a splitting point such that the amount of data greater than or equal to it and the amount less than or equal to it are the same — hence it's also called the "50% quantile." If $n$ is odd, the median equals the $(n+1)/2$-th largest number in the data; if $n$ is even, then any number between the $n/2$-th largest and the $n/2+1$-th largest can be regarded as the median, and in general we take their average.

The median's definition already reveals its resistance to interference: as long as the relative ordering of each number with respect to the median doesn't change, the median itself won't change. We can go further and introduce the "breakdown point" to describe this kind of robustness — it's defined as "the smallest proportion of outliers needed to make the result blow up to infinity." For the mean, the answer is essentially 0, since a single point going to infinity is enough to make the mean blow up too. But for the median, it's 50%, because more than half the data points need to go to infinity before the median does.

The drawback of the median is that it's more complex to compute than the mean, since it requires at least some degree of sorting the data — which is particularly unfriendly to distributed computing scenarios. Fortunately, most use cases don't require an extremely precise median either, so there's some room to maneuver. For example, one can compute local medians and then take a global average or median over those, which noticeably reduces communication overhead.

An Optimization Perspective

Interestingly, we can unify the mean and the median under an optimization perspective:

\begin{gather}\newcommand{argmin}{\mathop{\text{argmin}}}\newcommand{median}{\mathop{\text{median}}} \mean(x_1,x_2,\cdots,x_n) = \argmin_{\mu} \sum_{i=1}^n (x_i - \mu)^2 \\ \median(x_1,x_2,\cdots,x_n) = \argmin_{\mu} \sum_{i=1}^n |x_i - \mu| \\ \end{gather}

The proof for $\mean$ is fairly simple and left to the reader; here I'll briefly walk through the proof for $\median$. Without loss of generality, suppose $x_i$ is already sorted, i.e., $x_1\leq x_2\leq\cdots\leq x_n$, and let $f(\mu) = \sum_{i=1}^n |x_i - \mu|$. Taking the derivative directly gives

\begin{equation}\newcommand{sign}{\mathop{\text{sign}}} f'(\mu) = \sum_{i=1}^n \sign(\mu - x_i) = \#\{x_i < \mu\} - \#\{x_i > \mu\}\\ \end{equation}

The notation $\#$ denotes the count of items satisfying the given condition. To find the minimum, we want the derivative to be as close to 0 as possible, i.e., we want the number of $x_i$ greater than $\mu$ to be as close as possible to the number less than $\mu$ — which already matches the intuition behind the median. A more detailed discussion requires splitting into cases:

\begin{equation}f'(\mu) = \left\{\begin{aligned}&\left.\begin{aligned} &\underbrace{\#\{x_i < \mu\}}_{\leq k} - \underbrace{\#\{x_i > \mu\}}_{\geq k+1} < 0, &\mu < x_{k+1} \\ &\underbrace{\#\{x_i < \mu\}}_{\geq k+1} - \underbrace{\#\{x_i > \mu\}}_{\leq k} > 0, &\mu > x_{k+1} \\\end{aligned}\right\} & n = 2k+1 \\ &\left.\begin{aligned} &\underbrace{\#\{x_i < \mu\}}_{\leq k-1} - \underbrace{\#\{x_i > \mu\}}_{\geq k+1} < 0, &\mu < x_{k\phantom{+1}} \\ &\underbrace{\#\{x_i < \mu\}}_{\geq k+1} - \underbrace{\#\{x_i > \mu\}}_{\leq k-1} > 0, &\mu > x_{k+1} \\ \end{aligned}\right\} & n = 2k \end{aligned}\right.\end{equation}

That is, when $n$ is odd, $2k+1$, both $\mu < x_{k+1}$ and $\mu > x_{k+1}$ will make $f(\mu)$ increase, so $\mu^*=x_{k+1}$; when $n$ is even, $2k$, both $\mu < x_k$ and $\mu > x_{k+1}$ will make $f(\mu)$ increase, so $\mu^*\in [x_k, x_{k+1}]$, and one can check that when $\mu^*$ lies in this interval, $f(\mu^*)$ stays constant throughout, so every number in this interval is a valid $\mu^*$. In summary, $\mu^*$ matches exactly with the definition of the median.

Higher Dimensions

Working from the optimization perspective also helps us understand why the median resists the influence of outliers better than the mean: suppose there's one particularly large value $x_i$. Then the loss contributed by the mean is $(x_i - \mu)^2$, while for the median it's $|x_i - \mu|$, and in general $(x_i - \mu)^2 \gg |x_i - \mu|$, so the mean will lean more strongly toward the outlier, since doing so is what minimizes its loss.

Moreover, the optimization perspective has another advantage: it generalizes easily to higher dimensions. We know that the concept of the mean readily extends to higher dimensions — for a batch of vectors $\boldsymbol{x}_1,\boldsymbol{x}_2,\cdots,\boldsymbol{x}_n$, the mean vector is simply $\frac{1}{n}\sum_{i=1}^n \boldsymbol{x}_i$. The concept of the median, however, doesn't generalize as directly, since it relies on ordering, and it's hard to define a well-behaved order over vector-valued data.

Under the optimization perspective, though, this generalization becomes quite natural:

\begin{gather}\mean(\boldsymbol{x}_1,\boldsymbol{x}_2,\cdots,\boldsymbol{x}_n) = \argmin_{\boldsymbol{\mu}} \sum_{i=1}^n \Vert\boldsymbol{x}_i - \boldsymbol{\mu}\Vert_2^2 \\ \median(\boldsymbol{x}_1,\boldsymbol{x}_2,\cdots,\boldsymbol{x}_n) = \argmin_{\boldsymbol{\mu}} \sum_{i=1}^n \Vert\boldsymbol{x}_i - \boldsymbol{\mu}\Vert_2 \\ \end{gather}

where $\Vert\Vert_2$ is the Euclidean distance. It's easy to show that the mean vector defined this way is exactly $\frac{1}{n}\sum_{i=1}^n \boldsymbol{x}_i$, consistent with the usual empirical definition. As for the median vector, we also call it the "geometric median." Looking at the objective function, if $n=3$, this is exactly the classic "Fermat point" problem, which is why the median vector is often directly referred to as the Fermat point.

Unfortunately, the geometric median has no closed-form solution; it's usually computed using the following Weiszfeld iteration:

\begin{equation}\boldsymbol{\mu}_{t+1} = \frac{\sum_{i=1}^n \boldsymbol{x}_i / \Vert\boldsymbol{x}_i - \boldsymbol{\mu}_t\Vert_2}{\sum_{i=1}^n 1 / \Vert\boldsymbol{x}_i - \boldsymbol{\mu}_t\Vert_2}\end{equation}

Further Generalization

Naturally, we can consider an even more general formulation:

\begin{equation}\newcommand{average}{\mathop{\text{average}}}\average(\boldsymbol{x}_1,\boldsymbol{x}_2,\cdots,\boldsymbol{x}_n;\alpha) = \argmin_{\boldsymbol{\mu}} \sum_{i=1}^n \Vert\boldsymbol{x}_i - \boldsymbol{\mu}\Vert_2^{\alpha}\end{equation}

Writing $f(\boldsymbol{\mu}) = \sum_{i=1}^n \Vert\boldsymbol{x}_i - \boldsymbol{\mu}\Vert_2^{\alpha}$, we get

\begin{equation}\nabla_{\boldsymbol{\mu}} f(\boldsymbol{\mu}) = \alpha\sum_{i=1}^n \Vert\boldsymbol{x}_i - \boldsymbol{\mu}\Vert_2^{\alpha - 2}(\boldsymbol{\mu} - \boldsymbol{x}_i)\end{equation}

Letting $\nabla_{\boldsymbol{\mu}} f(\boldsymbol{\mu})=\boldsymbol{0}$, the equation we need to solve can be written as

\begin{equation}\boldsymbol{\mu} = \frac{\sum_{i=1}^n \Vert\boldsymbol{x}_i - \boldsymbol{\mu}\Vert_2^{\alpha - 2}\boldsymbol{x}_i}{\sum_{i=1}^n\Vert\boldsymbol{x}_i - \boldsymbol{\mu}\Vert_2^{\alpha - 2}}\end{equation}

Substituting $\boldsymbol{\mu}_t$ into the right-hand side and denoting the result as $\boldsymbol{\mu}_{t+1}$ gives us a fixed-point iteration. Substituting $\alpha=2$ recovers the mean vector, and substituting $\alpha=1$ recovers the Weiszfeld iteration. Strictly speaking, one should also prove convergence and uniqueness, but the details are fairly involved, so I'll skip them here.

Additionally, there's a less commonly used variant of the median vector in high-dimensional space, obtained by replacing the Euclidean norm with the L1 norm:

\begin{equation}\argmin_{\boldsymbol{\mu}} \sum_{i=1}^n \Vert\boldsymbol{x}_i - \boldsymbol{\mu}\Vert_1\end{equation}

This is called the "coordinate-wise median," since it essentially amounts to taking the one-dimensional median componentwise. It's simpler to compute, but since it lacks a clear geometric meaning, it's used less often in practice.

Summary

This post gave a brief overview of the concept and properties of the median, along with its generalization to higher-dimensional spaces.