HOME

TheInfoList



OR:

In
geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is ...
, the geometric median of a discrete set of sample points in a
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean ...
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 for one-dimensional data, and provides a
central tendency In statistics, a central tendency (or measure of central tendency) is a central or typical value for a probability distribution.Weisberg H.F (1992) ''Central Tendency and Variability'', Sage University Paper Series on Quantitative Applications in ...
in higher dimensions. It is also known as the 1-median, spatial median, Euclidean minisum point, or Torricelli point. The geometric median is an important
estimator In statistics, an estimator is a rule for calculating an estimate of a given quantity based on observed data: thus the rule (the estimator), the quantity of interest (the estimand) and its result (the estimate) are distinguished. For example, the ...
of
location In geography, location or place are used to denote a region (point, line, or area) on Earth's surface or elsewhere. The term ''location'' generally implies a higher degree of certainty than ''place'', the latter often indicating an entity with an ...
in statistics, where it is also known as the ''L''1 estimator. It is also a standard problem in
facility location Facility location is a name given to several different problems in computer science and in game theory Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: A ...
, where it models the problem of locating a facility to minimize the cost of transportation. The special case of the problem for three points in the plane (that is, = 3 and = 2 in the definition below) is sometimes also known as Fermat's problem; it arises in the construction of minimal
Steiner tree In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a n ...
s, and was originally posed as a problem by
Pierre de Fermat Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he ...
and solved by
Evangelista Torricelli Evangelista Torricelli ( , also , ; 15 October 160825 October 1647) was an Italian physicist and mathematician, and a student of Galileo. He is best known for his invention of the barometer, but is also known for his advances in optics and work ...
. Its solution is now known as the
Fermat point In Euclidean geometry, the Fermat point of a triangle, also called the Torricelli point or Fermat–Torricelli point, is a point such that the sum of the three distances from each of the three vertices of the triangle to the point is the smallest ...
of the triangle formed by the three sample points. 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 Alfred Weber (; 30 July 1868 – 2 May 1958) was a German economist, geographer, sociologist and theoretician of culture whose work was influential in the development of modern economic geography. Life Alfred Weber, younger brother of the ...
's discussion of the problem in his 1909 book on facility location. Some sources instead call Weber's problem the Fermat–Weber problem, but others use this name for the unweighted geometric median problem. provides a survey of the geometric median problem. See for generalizations of the problem to non-discrete point sets.


Definition

Formally, for a given set of ''m'' points x_1, x_2, \dots, x_m\, with each x_i \in \mathbb^n, the geometric median is defined as :\underset \sum_^m \left \, x_i-y \right \, _2 Here,
arg min In mathematics, the arguments of the maxima (abbreviated arg max or argmax) are the points, or elements, of the domain of some function at which the function values are maximized.For clarity, we refer to the input (''x'') as ''points'' and t ...
means the value of the argument y which minimizes the sum. In this case, it is the point y from where the sum of all
Euclidean distance In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefor ...
s to the x_i's is minimum.


Properties

* For the 1-dimensional case, the geometric median coincides with the median. This is because the
univariate In mathematics, a univariate object is an expression, equation, function or polynomial involving only one variable. Objects involving more than one variable are multivariate. In some cases the distinction between the univariate and multivariate ...
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 p_ 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 p_ and p_.) * The geometric median is unique whenever the points are not
collinear In geometry, collinearity of a set of points is the property of their lying on a single line. A set of points with this property is said to be collinear (sometimes spelled as colinear). In greater generality, the term has been used for aligned o ...
. * The geometric median is
equivariant In mathematics, equivariance is a form of symmetry for functions from one space with symmetry to another (such as symmetric spaces). A function is said to be an equivariant map when its domain and codomain are acted on by the same symmetry grou ...
for Euclidean similarity transformations, including
translation Translation is the communication of the meaning of a source-language text by means of an equivalent target-language text. The English language draws a terminological distinction (which does not exist in every language) between ''transla ...
and rotation. 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. * The geometric median has a
breakdown point Robust statistics are statistics with good performance for data drawn from a wide range of probability distributions, especially for distributions that are not normal. Robust statistical methods have been developed for many common problems, such ...
of 0.5. 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 Robust statistics are statistics with good performance for data drawn from a wide range of probability distributions, especially for distributions that are not normal distribution, normal. Robust Statistics, statistical methods have been developed ...
for the location of the uncorrupted data.


Special cases

*For 3 (non-
collinear In geometry, collinearity of a set of points is the property of their lying on a single line. A set of points with this property is said to be collinear (sometimes spelled as colinear). In greater generality, the term has been used for aligned o ...
) 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 each three pairs of triangle vertices. This is also known as the
Fermat point In Euclidean geometry, the Fermat point of a triangle, also called the Torricelli point or Fermat–Torricelli point, is a point such that the sum of the three distances from each of the three vertices of the triangle to the point is the smallest ...
of the triangle formed by the three vertices. (If the three points are collinear then the geometric median is the point between the two other points, as is the case with a one-dimensional median.) *For 4
coplanar In geometry, a set of points in space are coplanar if there exists a geometric plane that contains them all. For example, three points are always coplanar, and if the points are distinct and non-collinear, the plane they determine is unique. How ...
points, if one of the four points is inside the triangle formed by the other three points, then the geometric median is that point. Otherwise, the four points form a convex
quadrilateral In geometry a quadrilateral is a four-sided polygon, having four edges (sides) and four corners (vertices). The word is derived from the Latin words ''quadri'', a variant of four, and ''latus'', meaning "side". It is also called a tetragon, ...
and the geometric median is the crossing point of the diagonals of the quadrilateral. The geometric median of four coplanar points is the same as the unique
Radon point In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that any set of ''d'' + 2 points in R''d'' can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these convex ...
of the four points.


Computation

Despite the geometric median's being an easy-to-understand concept, computing it poses a challenge. The
centroid In mathematics and physics, the centroid, also known as geometric center or center of figure, of a plane figure or solid figure is the arithmetic mean position of all the points in the surface of the figure. The same definition extends to any ...
or center of mass, defined similarly to the geometric median as minimizing the sum of the ''squares'' of the distances to each point, can be found by a simple formula — its coordinates are the averages of the coordinates of the points — but it has been shown that no explicit formula, nor an exact algorithm involving only arithmetic operations and ''k''th roots, can exist in general for the geometric median. Therefore, only numerical or symbolic approximations to the solution of this problem are possible under this
model of computation In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how ...
. However, it is straightforward to calculate an approximation to the geometric median using an iterative procedure in which each step produces a more accurate approximation. Procedures of this type can be derived from the fact that the sum of distances to the sample points is a convex function, since the distance to each sample point is convex and the sum of convex functions remains convex. Therefore, procedures that decrease the sum of distances at each step cannot get trapped in a
local optimum In applied mathematics and computer science, a local optimum of an optimization problem is a solution that is optimal (either maximal or minimal) within a neighboring set of candidate solutions. This is in contrast to a global optimum, which ...
. One common approach of this type, called Weiszfeld's algorithm after the work of Endre Weiszfeld, is a form of
iteratively re-weighted least squares The method of iteratively reweighted least squares (IRLS) is used to solve certain optimization problems with objective functions of the form of a ''p''-norm: :\underset \sum_^n \big, y_i - f_i (\boldsymbol\beta) \big, ^p, by an iterative met ...
. This algorithm defines a set of weights that are inversely proportional to the distances from the current estimate to the sample points, and creates a new estimate that is the weighted average of the sample according to these weights. That is, :\left. y_=\left( \sum_^m \frac \right) \right/ \left( \sum_^m \frac \right). This method converges for almost all initial positions, but may fail to converge when one of its estimates falls on one of the given points. It can be modified to handle these cases so that it converges for all initial points. describe more sophisticated geometric optimization procedures for finding approximately optimal solutions to this problem. show how to compute the geometric median to arbitrary precision in nearly linear time. Note also that the problem can be formulated as the second-order cone program : \underset \ \sum_^m s_i \text s_i \geq \left \, x_i-y \right \, _2 \text i=1, \ldots, m, which can be solved in polynomial time using common optimization solvers.


Characterization of the geometric median

If ''y'' is distinct from all the given points, ''x''''i'', then ''y'' is the geometric median if and only if it satisfies: :0 = \sum_^m \frac . This is equivalent to: :\left. y = \left( \sum_^m \frac \right) \right/ \left( \sum_^m \frac \right), which is closely related to Weiszfeld's algorithm. In general, ''y'' is the geometric median if and only if there are vectors ''u''''i'' such that: :0 = \sum_^m u_i where for ''x''''i'' ≠ ''y'', :u_i = \frac and for ''x''''i'' = ''y'', :\, u_i \, \leq 1 . An equivalent formulation of this condition is :\sum _ \frac \le \left, \\. It can be seen as a generalization of the median property, in the sense that any partition of the points, in particular as induced by any hyperplane through ''y'', has the same and opposite sum of positive ''directions'' from ''y'' on each side. In the one dimensional case, the hyperplane is the point ''y'' itself, and the sum of directions simplifies to the (directed) counting measure.


Generalizations

The geometric median can be generalized from Euclidean spaces to general Riemannian manifolds (and even
metric space In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general set ...
s) using the same idea which is used to define the
Fréchet mean In mathematics and statistics, the Fréchet mean is a generalization of centroids to metric spaces, giving a single representative point or central tendency for a cluster of points. It is named after Maurice Fréchet. Karcher mean is the renaming o ...
on a Riemannian manifold. Let M be a Riemannian manifold with corresponding distance function d(\cdot, \cdot), let w_1, \ldots, w_n be n weights summing to 1, and let x_1, \ldots, x_n be n observations from M. Then we define the weighted geometric median m (or weighted Fréchet median) of the data points as : m = \underset \sum_^n w_i d(x,x_i) . If all the weights are equal, we say simply that m is the geometric median.


See also

*
Medoid Medoids are representative objects of a data set or a cluster within a data set whose sum of dissimilarities to all the objects in the cluster is minimal. Medoids are similar in concept to means or centroids, but medoids are always restricted to be ...
* Geometric median absolute deviation


Notes


References

* * * * * * * * * * * * * * * * * * * *. * * * * * Translated into English as {{refend Means Multivariate statistics Nonparametric statistics Mathematical optimization Geometric algorithms Descriptive statistics