Geometric median

Last updated March 17, 2024

In geometry, the geometric median of a discrete set of sample points 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 for one-dimensional data, and provides a central tendency in higher dimensions. It is also known as the spatial median,^[1]Euclidean minisum point,^[1], Torricelli point, ^[2] or 1-median.

The geometric median is an important estimator of location in statistics,^[3] because it minimizes the sum of the L₂ distances of the samples.^[4] It is to be compared to the mean, which minimizes the sum of the squared L₂ distances, and to the coordinate-wise median which minimizes the sum of the L₁ distances. It is also a standard problem in facility location, where it models the problem of locating a facility to minimize the cost of transportation.^[5] The more general k-median problem asks for the location of k cluster centers minimizing the sum of L₂ 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

Formally, for a given set of m points $\mathbb {X} ^{m}=x_{1},x_{2},\dots ,x_{m}\,$ with each $x_{i}\in \mathbb {R} ^{n}$ , the geometric median is defined as the sum of the L₂ distances minimizer

{\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 $y$ which minimizes the sum. In this case, it is the point $y$ in n dimensional Euclidean space from where the sum of all Euclidean distances 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 median also minimizes the sum of distances from the points. (More precisely, if the points are p₁, ..., p_n, in that order, the geometric median is the middle point $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 $p_{n/2}$ and $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

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 each three pairs of triangle vertices.^[10] This is also known as the Fermat point 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 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 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 of the four points.^[14]

Computation

Despite the geometric median's being an easy-to-understand concept, computing it poses a challenge. The centroid 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 kth 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.^[15]

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.

One common approach of this type, called Weiszfeld's algorithm after the work of Endre Weiszfeld,^[16] is a form of iteratively re-weighted least squares. 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_{k+1}=\left(\sum _{i=1}^{m}{\frac {x_{i}}{\|x_{i}-y_{k}\|}}\right)\right/\left(\sum _{i=1}^{m}{\frac {1}{\|x_{i}-y_{k}\|}}\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.^[12]

Bose, Maheshwari & Morin (2003) describe more sophisticated geometric optimization procedures for finding approximately optimal solutions to this problem. Cohen et al. (2016) 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 {y\in \mathbb {R} ^{n},\ s\in \mathbb {R} ^{m}}{\min }}\ \sum _{i=1}^{m}s_{i}{\text{ subject to }}s_{i}\geq \left\|x_{i}-y\right\|_{2}{\text{ for }}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 _{i=1}^{m}{\frac {x_{i}-y}{\left\|x_{i}-y\right\|}}.

This is equivalent to:

\left.y=\left(\sum _{i=1}^{m}{\frac {x_{i}}{\|x_{i}-y\|}}\right)\right/\left(\sum _{i=1}^{m}{\frac {1}{\|x_{i}-y\|}}\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 _{i=1}^{m}u_{i}

where for x_i ≠ y,

u_{i}={\frac {x_{i}-y}{\left\|x_{i}-y\right\|}}

and for x_i = y,

\|u_{i}\|\leq 1.

An equivalent formulation of this condition is

\sum _{1\leq i\leq m,x_{i}\neq y}{\frac {x_{i}-y}{\left\|x_{i}-y\right\|}}\leq \left|\{\,i\mid 1\leq i\leq m,x_{i}=y\,\}\right|.

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 spaces) using the same idea which is used to define the Fréchet mean on a Riemannian manifold.^[17]^[18] 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 {x\in M}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}d(x,x_{i})

.

If all the weights are equal, we say simply that $m$ is the geometric median.

Notes

1 2 3 Drezner et al. (2002)
↑ Cieslik (2006).
↑ Lawera & Thompson (1993).
↑ Dodge & Rousson (1999).
↑ Eiselt & Marianov (2011).
↑ Krarup & Vajda (1997).
↑ Spain (1996).
↑ Brimberg (1995).
↑ Bose, Maheshwari & Morin (2003).
1 2 3 Haldane (1948)
↑ Claim 18.10, Geometric Methods and Optimization Problems, V. Boltyanski, H. Martini, V. Soltan, Springer, 1999.
1 2 Vardi & Zhang (2000)
1 2 3 Lopuhaä & Rousseeuw (1991)
↑ Cieslik (2006), p. 6; Plastria (2006). The convex case was originally proven by Giovanni Fagnano.
↑ Bajaj (1986); Bajaj (1988). Earlier, Cockayne & Melzak (1969) proved that the Steiner point for 5 points in the plane cannot be constructed with ruler and compass
↑ Weiszfeld (1937); Kuhn (1973); Chandrasekaran & Tamir (1989).
↑ Fletcher, P. Thomas; Venkatasubramanian, Suresh; Joshi, Sarang (23 June 2008). "Robust statistics on Riemannian manifolds via the geometric median". 2008 IEEE Conference on Computer Vision and Pattern Recognition. IEEE Conference on Computer Vision and Pattern Recognition. Anchorage, AK, USA: IEEE.
↑ Fletcher, Venkatasubramanian & Joshi (2009).

Related Research Articles

In statistics, a central tendency is a central or typical value for a probability distribution.

Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's Elements, it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean spaces of any positive integer dimension n, which are called Euclidean n-spaces when one wants to specify their dimension. For n equal to one or two, they are commonly called respectively Euclidean lines and Euclidean planes. The qualifier "Euclidean" is used to distinguish Euclidean spaces from other spaces that were later considered in physics and modern mathematics.

In statistics, the Kolmogorov–Smirnov test is a nonparametric test of the equality of continuous, one-dimensional probability distributions that can be used to test whether a sample came from a given reference probability distribution, or to test whether two samples came from the same distribution. Intuitively, the test provides a method to qualitatively answer the question "How likely is it that we would see a collection of samples like this if they were drawn from that probability distribution?" or, in the second case, "How likely is it that we would see two sets of samples like this if they were drawn from the same probability distribution?". It is named after Andrey Kolmogorov and Nikolai Smirnov.

In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution. For a data set, it may be thought of as "the middle" value. The basic feature of the median in describing data compared to the mean is that it is not skewed by a small proportion of extremely large or small values, and therefore provides a better representation of the center. Median income, for example, may be a better way to describe the center of the income distribution because increases in the largest incomes alone have no effect on the median. For this reason, the median is of central importance in robust statistics.

In probability theory, Chebyshev's inequality provides an upper bound on the probability of deviation of a random variable from its mean. More specifically, the probability that a random variable deviates from its mean by more than $is at most, where is any positive constant.$

<span class="mw-page-title-main">Centroid</span> Mean position of all the points in a shape

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 object in $-dimensional Euclidean space.$

This is a glossary of some terms used in Riemannian geometry and metric geometry — it doesn't cover the terminology of differential topology.

The Mahalanobis distance is a measure of the distance between a point $and a distribution, introduced by P. C. Mahalanobis in 1936. Mahalanobis's definition was prompted by the problem of identifying the similarities of skulls based on measurements in 1927.$

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.

In mathematics, Hilbert's fourth problem in the 1900 list of Hilbert's problems is a foundational question in geometry. In one statement derived from the original, it was to find — up to an isomorphism — all geometries that have an axiomatic system of the classical geometry, with those axioms of congruence that involve the concept of the angle dropped, and `triangle inequality', regarded as an axiom, added.

k-means clustering is a method of vector quantization, originally from signal processing, that aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean, serving as a prototype of the cluster. This results in a partitioning of the data space into Voronoi cells. k-means clustering minimizes within-cluster variances, but not regular Euclidean distances, which would be the more difficult Weber problem: the mean optimizes squared errors, whereas only the geometric median minimizes Euclidean distances. For instance, better Euclidean solutions can be found using k-medians and k-medoids.

<span class="mw-page-title-main">Varignon frame</span>

The Varignon frame, named after Pierre Varignon, is a mechanical device which can be used to determine an optimal location of a warehouse for the destribution of goods to a set of shops. Optimal means that the sum of the weighted distances of the shops to the warehouse should be minimal. The frame consists of a board with n holes corresponding to the n shops at the locations $, n strings are tied together in a knot at one end, the loose ends are passed, one each, through the holes and are attached to weights below the board. If the influence of friction and other odds of the real world are neglected, the knot will take a position of equilibrium . It can be shown, that point is the optimal location which minimizes the weighted sum of distances$

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 possible or, equivalently, the geometric median of the three vertices. It is so named because this problem was first raised by Fermat in a private letter to Evangelista Torricelli, who solved it.

In mathematics, a Euclidean distance matrix is an $n \times n$ matrix representing the spacing of a set of $n$ points in Euclidean space. For points $in k -dimensional space ℝ k, the elements of their Euclidean distance matrix A are given by squares of distances between them. That is$

The study of facility location problems (FLP), also known as location analysis, is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering factors like avoiding placing hazardous materials near housing, and competitors' facilities. The techniques also apply to cluster analysis.

Mean shift is a non-parametric feature-space mathematical analysis technique for locating the maxima of a density function, a so-called mode-seeking algorithm. Application domains include cluster analysis in computer vision and image processing.

<span class="mw-page-title-main">Pu's inequality</span>

In differential geometry, Pu's inequality, proved by Pao Ming Pu, relates the area of an arbitrary Riemannian surface homeomorphic to the real projective plane with the lengths of the closed curves contained in it.

In differential geometry, Mikhail Gromov's filling area conjecture asserts that the hemisphere has minimum area among the orientable surfaces that fill a closed curve of given length without introducing shortcuts between its points.

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 of the Riemannian Center of Mass construction developed by Karsten Grove and Hermann Karcher. On the real numbers, the arithmetic mean, median, geometric mean, and harmonic mean can all be interpreted as Fréchet means for different distance functions.

In geometry, the Weber problem, named after Alfred Weber, is one of the most famous problems in location theory. It requires finding a point in the plane that minimizes the sum of the transportation costs from this point to $n$ destination points, where different destination points are associated with different costs per unit distance.

References

Bajaj, Chanderjit (1986). "Proving geometric algorithms nonsolvability: An application of factoring polynomials". Journal of Symbolic Computation . 2: 99–102. doi: 10.1016/S0747-7171(86)80015-3 .
Bajaj, Chanderjit (1988). "The algebraic degree of geometric optimization problems". Discrete & Computational Geometry . 3 (2): 177–191. doi: 10.1007/BF02187906 .
Bose, Prosenjit; Maheshwari, Anil; Morin, Pat (2003). "Fast approximations for sums of distances, clustering and the Fermat–Weber problem". Computational Geometry: Theory and Applications . 24 (3): 135–146. doi: 10.1016/S0925-7721(02)00102-5 .
Brimberg, J. (1995). "The Fermat–Weber location problem revisited". Mathematical Programming . 71 (1, Ser. A): 71–76. doi:10.1007/BF01592245. MR 1362958. S2CID 206800756.
Chandrasekaran, R.; Tamir, A. (1989). "Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem". Mathematical Programming . Series A. 44 (1–3): 293–295. doi:10.1007/BF01587094. S2CID 43224801.
Cieslik, Dietmar (2006). Shortest Connectivity: An Introduction with Applications in Phylogeny. Combinatorial Optimization. Vol. 17. Springer. p. 3. ISBN 9780387235394.
Cockayne, E. J.; Melzak, Z. A. (1969). "Euclidean constructability in graph minimization problems". Mathematics Magazine . 42 (4): 206–208. doi:10.2307/2688541. JSTOR 2688541.
Cohen, Michael; Lee, Yin Tat; Miller, Gary; Pachocki, Jakub; Sidford, Aaron (2016). "Geometric median in nearly linear time" (PDF). Proc. 48th Symposium on Theory of Computing (STOC 2016). Association for Computing Machinery. arXiv: 1606.05225 . doi:10.1145/2897518.2897647.
Dodge, Yadolah; Rousson, Valentin (September 1999). "Multivariate $L 1$ mean". Metrika. 49 (2): 127–134. doi:10.1007/s001840050029.
Drezner, Zvi; Klamroth, Kathrin; Schöbel, Anita; Wesolowsky, George O. (2002). "The Weber problem". Facility Location: Applications and Theory. Springer, Berlin. pp. 1–36. ISBN 9783540213451. MR 1933966.
Eiselt, H. A.; Marianov, Vladimir (2011). Foundations of Location Analysis. International Series in Operations Research & Management Science. Vol. 155. Springer. p. 6. ISBN 9781441975720.
Fekete, Sándor P.; Mitchell, Joseph S. B.; Beurer, Karin (2005). "On the continuous Fermat-Weber problem". Operations Research . 53 (1): 61–76. arXiv: cs.CG/0310027 . doi:10.1287/opre.1040.0137. S2CID 1121.
Fletcher, P. Thomas; Venkatasubramanian, Suresh; Joshi, Sarang (2009). "The geometric median on Riemannian manifolds with application to robust atlas estimation". NeuroImage. 45 (1 Suppl): s143–s152. doi:10.1016/j.neuroimage.2008.10.052. PMC 2735114 . PMID 19056498.
Haldane, J. B. S. (1948). "Note on the median of a multivariate distribution". Biometrika. 35 (3–4): 414–417. doi:10.1093/biomet/35.3-4.414.
Krarup, Jakob; Vajda, Steven (1997). "On Torricelli's geometrical solution to a problem of Fermat". IMA Journal of Mathematics Applied in Business and Industry. 8 (3): 215–224. doi:10.1093/imaman/8.3.215. MR 1473041.
Kuhn, Harold W. (1973). "A note on Fermat's problem". Mathematical Programming . 4 (1): 98–107. doi:10.1007/BF01584648. S2CID 22534094.
Lawera, Martin; Thompson, James R. (1993). "Some problems of estimation and testing in multivariate statistical process control" (PDF). Proceedings of the 38th Conference on the Design of Experiments. U.S. Army Research Office Report. Vol. 93–2. pp. 99–126. Archived from the original on May 17, 2014.
Lopuhaä, Hendrick P.; Rousseeuw, Peter J. (1991). "Breakdown points of affine equivariant estimators of multivariate location and covariance matrices". Annals of Statistics . 19 (1): 229–248. doi: 10.1214/aos/1176347978 . JSTOR 2241852.
Nie, Jiawang; Parrilo, Pablo A.; Sturmfels, Bernd (2008). "Semidefinite representation of the $k$ -ellipse". In Dickenstein, A.; Schreyer, F.-O.; Sommese, A.J. (eds.). Algorithms in Algebraic Geometry. IMA Volumes in Mathematics and its Applications. Vol. 146. Springer-Verlag. pp. 117–132. arXiv: math/0702005 . Bibcode:2007math......2005N. doi:10.1007/978-0-387-75155-9_7. S2CID 16558095.
Ostresh, L. (1978). "Convergence of a class of iterative methods for solving Weber location problem". Operations Research . 26 (4): 597–609. doi:10.1287/opre.26.4.597.
Plastria, Frank (2006). "Four-point Fermat location problems revisited. New proofs and extensions of old results" (PDF). IMA Journal of Management Mathematics. 17 (4): 387–396. doi:10.1093/imaman/dpl007. Zbl 1126.90046..
Spain, P. G. (1996). "The Fermat point of a triangle". Mathematics Magazine. 69 (2): 131–133. doi:10.1080/0025570X.1996.11996409. JSTOR 2690672?origin=pubexport. MR 1573157.
Vardi, Yehuda; Zhang, Cun-Hui (2000). "The multivariate $L 1$ -median and associated data depth". Proceedings of the National Academy of Sciences of the United States of America. 97 (4): 1423–1426 (electronic). Bibcode:2000PNAS...97.1423V. doi: 10.1073/pnas.97.4.1423 . MR 1740461. PMC 26449 . PMID 10677477.
Weber, Alfred (1909). Über den Standort der Industrien, Erster Teil: Reine Theorie des Standortes (in German). Tübingen: Mohr.
Wesolowsky, G. (1993). "The Weber problem: History and perspective". Location Science. 1: 5–23.
Weiszfeld, E. (1937). "Sur le point pour lequel la somme des distances de $n$ points donnes est minimum". Tohoku Mathematical Journal (in French). 43: 355–386. Translated into English as Weiszfeld, E.; Plastria, Frank (April 2008). "On the point for which the sum of the distances to $n$ given points is minimum". Annals of Operations Research . 167 (1): 7–41. doi:10.1007/s10479-008-0352-z. S2CID 21000317.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[dksw-1] 1 2 3 Drezner et al. (2002)

[FOOTNOTECieslik2006-2] Cieslik (2006).

[FOOTNOTELaweraThompson1993-3] Lawera & Thompson (1993).

[FOOTNOTEDodgeRousson1999-4] Dodge & Rousson (1999).

[FOOTNOTEEiseltMarianov2011-5] Eiselt & Marianov (2011).

[FOOTNOTEKrarupVajda1997-6] Krarup & Vajda (1997).

[FOOTNOTESpain1996-7] Spain (1996).

[FOOTNOTEBrimberg1995-8] Brimberg (1995).

[FOOTNOTEBoseMaheshwariMorin2003-9] Bose, Maheshwari & Morin (2003).

[haldane-10] 1 2 3 Haldane (1948)

[11] Claim 18.10, Geometric Methods and Optimization Problems, V. Boltyanski, H. Martini, V. Soltan, Springer, 1999.

[vz-12] 1 2 Vardi & Zhang (2000)

[lr-13] 1 2 3 Lopuhaä & Rousseeuw (1991)

[14] Cieslik (2006), p. 6; Plastria (2006). The convex case was originally proven by Giovanni Fagnano.

[15] Bajaj (1986); Bajaj (1988). Earlier, Cockayne & Melzak (1969) proved that the Steiner point for 5 points in the plane cannot be constructed with ruler and compass

[16] Weiszfeld (1937); Kuhn (1973); Chandrasekaran & Tamir (1989).

[17] Fletcher, P. Thomas; Venkatasubramanian, Suresh; Joshi, Sarang (23 June 2008). "Robust statistics on Riemannian manifolds via the geometric median". 2008 IEEE Conference on Computer Vision and Pattern Recognition. IEEE Conference on Computer Vision and Pattern Recognition. Anchorage, AK, USA: IEEE.

[FOOTNOTEFletcherVenkatasubramanianJoshi2009-18] Fletcher, Venkatasubramanian & Joshi (2009).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]