Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

If so, what? If not, why not?

For a sample on the line, the median minimizes the total absolute deviation. It would seem natural to extend the definition to R2, etc., but I've never seen it. But then, I've been out in left field for a long time.

share|improve this question

7 Answers 7

As @Ars said there are no accepted definition (and this is a good point). There are general alternatives families of ways to generalize quantiles on $\mathbb{R}^d$, I think the most significant are:

  • Generalize quantile process Let $P_n(A)$ be the empirical measure (=the proportion of observations in $A$). Then, with $\mathbb{A}$ a well chosen subset of the Borel sets in $\mathbb{R}^d$ and $\lambda$ a real valued measure, you can define the empirical quantile function:

    $U_n(t)=\inf (\lambda(A) : P_n(A)\geq t A\in\mathbb{A})$

    Suppose you can find one $A_{t}$ that gives you the minimum. Then the set (or an element of the set) $A_{1/2-\epsilon}\cap A_{1/2+\epsilon}$ gives you the median when $\epsilon$ is made small enough. The definition of the median is recovered when using $\mathbb{A}=(]-\infty,x] x\in\mathbb{R})$ and $\lambda(]-\infty,x])=x$. Ars answer falls into that framework I guess... tukey's half space location may be obtained using $\mathbb{A}(a)=( H_{x}=(t\in \mathbb{R}^d :\; \langle a, t \rangle \leq x ) $ and $\lambda(H_{x})=x$ (with $x\in \mathbb{R}$, $a\in\mathbb{R}^d$).

  • variational definition and M-estimation The idea here is that the $\alpha$-quantile $Q_{\alpha}$ of a random variable $Y$ in $\mathbb{R}$ can be defined through a variational equality.

    • The most common definition is using the quantile regression function $\rho_{\alpha}$ (also known as pinball loss, guess why ? ) $Q_{\alpha}=arg\inf_{x\in \mathbb{R}}\mathbb{E}[\rho_{\alpha}(Y-x)]$. The case $\alpha=1/2$ gives $\rho_{1/2}(y)=|y|$ and you can generalize that to higher dimension using $l^1$ distances as done in @Srikant Answer. This is theoretical median but gives you empirical median if you replace expectation by empirical expectation (mean).

    • But Kolshinskii proposes to use Legendre-Fenchel transform: since $Q_{\alpha}=Arg\sup_s (s\alpha-f(s))$ where $f(s)=\frac{1}{2}\mathbb{E} [|s-Y|-|Y|+s]$ for $s\in \mathbb{R}$. He gives a lot of deep reasons for that (see the paper ;)). Generalizing this to higher dimensions require working with a vectorial $\alpha$ and replacing $s\alpha$ by $\langle s,\alpha\rangle$ but you can take $\alpha=(1/2,\dots,1/2)$.

  • Partial ordering You can generalize the definition of quantiles in $\mathbb{R}^d$ as soon as you can create a partial order (with equivalence classes).

Obviously there are bridges between the different formulations. They are not all obvious...

share|improve this answer
    
Nice answer, Robin! –  ars Aug 20 '10 at 18:07

I'm not sure there is one accepted definition for a multivariate median. The one I'm familiar with is Oja's median point, which minimizes the sum of volumes of simplices formed over subsets of points. (See the link for a technical definition.)

Update: The site referenced for the Oja definition above also has a nice paper covering a number of definitions of a multivariate median:

share|improve this answer
    
Nice reference: thanks. It comprehensively covers everything mentioned here. –  whuber Aug 19 '10 at 21:03

There are distinct ways to generalize the concept of median to higher dimensions. One not yet mentioned, but which was proposed long ago, is to construct a convex hull, peel it away, and iterate for as long as you can: what's left in the last hull is a set of points that are all candidates to be "medians."

"Head-banging" is another more recent attempt (c. 1980) to construct a robust center to a 2D point cloud.

The principal reason why there are multiple distinct generalizations and no one obvious solution is that R1 can be ordered but R2, R3, ... cannot be.

share|improve this answer
    
Any measure that coincides with the usual median when restricted to R1 is a candidate generalization. There must be a lot of them. –  phv3773 Aug 24 '10 at 19:37
    
phv:> one can ask for 'the' generalization to preserve (in higher dimensions) some of the interesting properties of the median. This severly limits the number of candidates (see the commenting after Srikant's answer below) –  user603 Sep 20 '10 at 20:10
    
@Whuber:> then notion of ordering can be generalized to R^n for unimodal distributions (see my answer below). –  user603 Sep 20 '10 at 20:11
    
@kwak: could you elaborate a little? The usual mathematical definition of an ordering of a space is independent of any kind of probability distribution, so you must implicitly have some additional assumptions in mind. –  whuber Sep 20 '10 at 21:14
    
@Whuber:> You state: "R1 can be ordered but R2, R3, ... cannot be". R2,..,R3 can be ordered in many ways by mapping from Rn to R . One such way is the tukey depth. It has many important properties (robustness to some extend, non parametric, invariance,...) but these only hold for the case of unimodal distributions. Let me know if you want more details. –  user603 Sep 21 '10 at 1:47

Geometric median is the point with the smallest average euclidian distance from the samples

share|improve this answer

A definition that comes close to it, for unimodal distributions, is the tukey halfspace median

http://cgm.cs.mcgill.ca/~athens/Geometric-Estimators/halfspace.html http://www.isical.ac.in/~statmath/html/publication/Tukey_tech_rep.pdf

share|improve this answer

The Tukey halfspace median can be extended to >2 dimensions using DEEPLOC, an algorithm due to Struyf and Rousseeuw; see here for details.

The algorithm is used to approximate the point of greatest depth efficiently; naive methods which attempt to determine this exactly usually run afoul of (the computational version of) "the curse of dimensionality", where the runtime required to calculate a statistic grows exponentially with the number of dimensions of the space.

share|improve this answer

I do not know if any such definition exists but I will try and extend the standard definition of the median to $R^2$. I will use the following notation:

$X$, $Y$: the random variables associated with the two dimensions.

$m_x$, $m_y$: the corresponding medians.

$f(x,y)$: the joint pdf for our random variables

To extend the definition of the median to $R^2$, we choose $m_x$ and $m_y$ to minimize the following:

$E(|(x,y) - (m_x,m_y)|$

The problem now is that we need a definition for what we mean by:

$|(x,y) - (m_x,m_y)|$

The above is in a sense a distance metric and several possible candidate definitions are possible.

Eucliedan Metric

$|(x,y) - (m_x,m_y)| = \sqrt{(x-m_x)^2 + (y-m_y)^2}$

Computing the median under the euclidean metric will require computing the expectation of the above with respect to the joint density $f(x,y)$.

Taxicab Metric

$|(x,y) - (m_x,m_y)| = |x-m_x| + |y-m_y|$

Computing the median in the case of the taxicab metric involves computing the median of $X$ and $Y$ separately as the metric is separable in $x$ and $y$.

share|improve this answer
    
Srikant:> No. The definition has to have two important feature of the univariate median. a) Invariant to monotone transformation of the data, b) robust to contamination by outliers. None of the extentions you propose have these. The Tukey depth has these qualities. –  user603 Sep 20 '10 at 16:57
    
@kwak What you say makes sense. –  user28 Sep 20 '10 at 18:25
    
@Srikant:> Check the R&S paper cited by Gary Campbell above ;). Best, –  user603 Sep 20 '10 at 18:38
    
@kwak On thinking some more, the taxicab metric does have the features you mentioned as it basically reduces to univariate medians. no? –  user28 Sep 20 '10 at 18:40
1  
@Srikant:> there are no incorrect answer to phv's questions because there are no 'good answers' either; this area of research is still under development. I simply wanted to point out why it is still an open problem. –  user603 Sep 20 '10 at 20:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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