Geometric median - Wikipedia
Jump to content
Search
Search
Donate
Create account
Log in
Personal tools
Donate
Create account
Log in
Geometric median
8 languages
Español<br>Français<br>עברית<br>한국어<br>Română<br>Русский<br>Türkçe<br>Українська
Edit links
From Wikipedia, the free encyclopedia
Point minimizing sum of distances to given points
Not to be confused with Median (geometry) or Geometric mean.
Example of geometric median (in yellow) of a series of points. In blue the Center of mass.
In geometry, the geometric median of a discrete point set in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances or absolute differences for one-dimensional data. It is also known as the spatial median ,[1] Euclidean minisum point ,[1] Torricelli point , [2] or 1-median . It provides a measure of central tendency in higher dimensions and it is a standard problem in facility location, i.e., locating a facility to minimize the cost of transportation.[3]
The geometric median is an important estimator of location in statistics,[4] because it minimizes the sum of the L2 distances of the samples.[5] It is to be compared to the mean, which minimizes the sum of the squared L2 distances; and to the coordinate-wise median which minimizes the sum of the L1 distances.<br>The more general k-median problem asks for the location of k cluster centers minimizing the sum of L2 distances from each sample point to its nearest center.
The special case of the problem for three points in the plane (that is, m = 3 and n = 2 in the definition below) is sometimes also known as Fermat's problem ; it arises in the construction of minimal Steiner trees, and was originally posed as a problem by Pierre de Fermat and solved by Evangelista Torricelli.[6] Its solution is now known as the Fermat point of the triangle formed by the three sample points.[7] The geometric median may in turn be generalized to the problem of minimizing the sum of weighted distances, known as the Weber problem after Alfred Weber's discussion of the problem in his 1909 book on facility location.[1] Some sources instead call Weber's problem the Fermat–Weber problem,[8] but others use this name for the unweighted geometric median problem.[9]
Wesolowsky (1993) provides a survey of the geometric median problem. See Fekete, Mitchell & Beurer (2005) for generalizations of the problem to non-discrete point sets.
Definition<br>[edit]
Formally, for a given set of m points
{\displaystyle \mathbb {X} ^{m}=x_{1},x_{2},\dots ,x_{m}\,}
with each
{\displaystyle x_{i}\in \mathbb {R} ^{n}}
, the geometric median is defined as the minimizer of the sum of the L2 distances:
{\displaystyle {\underset {y\in \mathbb {R} ^{n}}{\operatorname {arg\,min} }}\sum _{i=1}^{m}\left\|x_{i}-y\right\|_{2}\,.}
Here, arg min means the value of the argument
{\displaystyle y}
which minimizes the sum. In this case, it is the point
{\displaystyle y}
in n-dimensional Euclidean space from where the sum of all Euclidean distances to the
{\displaystyle x_{i}}
's is minimum.
Properties<br>[edit]
For the 1-dimensional case, the geometric median coincides with the median. This is because the univariate median also minimizes the sum of distances from the points. (More precisely, if the points are p1, ..., pn, in that order, the geometric median is the middle point
{\displaystyle p_{(n+1)/2}}
if n is odd, but is not uniquely determined if n is even, when it can be any point in the line segment between the two middling points
{\displaystyle p_{n/2}}
and
{\displaystyle p_{(n/2)+1}}
.) [10][11]
The geometric median is unique whenever the points are not collinear.[12]
The geometric median is equivariant for Euclidean similarity transformations, including translation and rotation.[13][10] This means that one would get the same result either by transforming the geometric median, or by applying the same transformation to the sample data and finding the geometric median of the transformed data. This property follows from the fact that the geometric median is defined only from pairwise distances, and does not depend on the system of orthogonal Cartesian coordinates by which the sample data is represented. In contrast, the component-wise median for a multivariate data set is not in general rotation invariant, nor is it independent of the choice of coordinates.[13]
The geometric median has a breakdown point of 0.5.[13] 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.
Special cases<br>[edit]
For 3 (non-collinear) points, if any angle of the triangle formed by those points is 120° or more, then the geometric median is the point at the vertex of that angle. If all the angles are less than 120°, the geometric median is the point inside the triangle which subtends an angle of 120° to...