Definition The geometric median of a discrete set of points in a Euclidean space is the point that minimizes the sum of Euclidean distances to these points. It is a robust estimator of location, representing a measure of central tendency.
Overview The geometric median is a fundamental concept in geometry, statistics, and optimization. Unlike the arithmetic mean (centroid), which minimizes the sum of squared distances, the geometric median minimizes the sum of actual (linear) distances. This property makes it less sensitive to outliers, rendering it a more robust measure of central location in multivariate data analysis. It is also known as the spatial median or $L_1$ median, in contrast to the arithmetic mean, which is the $L_2$ mean. While the arithmetic mean has a simple closed-form solution, the geometric median generally does not, requiring iterative numerical methods for its computation, such as Weiszfeld's algorithm. Its applications span various fields, including facility location problems, sensor network localization, and robust statistics.
Etymology/Origin The problem of finding a point that minimizes the sum of distances to a given set of points dates back to the 17th century. For three points in a plane, this problem is known as Fermat's problem or the Fermat-Torricelli problem, posed by Pierre de Fermat and later solved geometrically by Evangelista Torricelli. Torricelli's solution for three points identified the point now known as the Fermat point. The generalization of this concept to an arbitrary number of points and higher dimensions, leading to the "geometric median," gained significant attention with modern optimization theory. Edmund Weiszfeld published an iterative algorithm for its computation in 1937, though his work was not widely recognized until later.
Characteristics
- Uniqueness: For a set of points that are not all collinear, the geometric median is unique. If all points lie on a single line, any point on the segment defined by the 1D median of the points can be a geometric median. More precisely, if all points are collinear, the geometric median is the standard one-dimensional median of the points.
- No Closed-Form Expression: Generally, there is no direct analytical formula to compute the geometric median. It typically requires iterative numerical methods.
- Robustness: It is less susceptible to the influence of outliers compared to the arithmetic mean. A single point moved far away will shift the geometric median less dramatically than the arithmetic mean.
- Location within Convex Hull: The geometric median of a set of points is always contained within the convex hull of those points.
- Invariance to Rotation and Scaling: The geometric median is invariant to Euclidean transformations (translation, rotation, reflection) and scaling, meaning that transforming the input points and then finding the median yields the same result as finding the median and then transforming it.
Related Topics
- Fermat Point / Fermat-Torricelli Problem: The specific case of the geometric median for three points.
- Spatial Median / L1 Median: Synonymous terms for the geometric median.
- Weiszfeld's Algorithm: A widely used iterative algorithm for computing the geometric median.
- Robust Statistics: The field of statistics that deals with methods resilient to outliers, where the geometric median plays a crucial role.
- Facility Location Problem: A class of optimization problems where the geometric median often determines the optimal location for a facility to minimize total travel distance.
- Arithmetic Mean (Centroid): A contrasting measure of central tendency that minimizes the sum of squared Euclidean distances ($L_2$ norm).
- Median (1D): The one-dimensional analogue of the geometric median, minimizing the sum of absolute deviations.