Geometric median explained

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, Euclidean minisum point, Torricelli point, or 1-median.

The geometric median is an important estimator of location in statistics, because it minimizes the sum of the L2 distances of the samples. 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. It is also a standard problem in facility location, where it models the problem of locating a facility to minimize the cost of transportation.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, = 3 and = 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. Its solution is now known as the Fermat point 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'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

Xm=x1,x2,...,xm

with each

xi\inRn

, the geometric median is defined as the sum of the L2 distances minimizer

\underset{y\inRn}{\operatorname{argmin}}

m
\sum
i=1

\left\|xi-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

xi

's is minimum.

Properties

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

pn/2

and

p(n/2)+1

.) [1]

Special cases

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.[3]

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,[4] 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.yk+1=\left(

m
\sum
i=1
xi
\|xi-yk\|

\right)\right/\left(

m
\sum
i=1
1
\|xi-yk\|

\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{y\inRn, s\inRm}{min}

m
 \sum
i=1

sisubjecttosi\geq\left\|xi-y\right\|2fori=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, xi, then y is the geometric median if and only if it satisfies:

0=

m
\sum
i=1
xi-y
\left\|xi-y\right\|

.

This is equivalent to:

\left.y=\left(

m
\sum
i=1
xi
\|xi-y\|

\right)\right/\left(

m
\sum
i=1
1
\|xi-y\|

\right),

which is closely related to Weiszfeld's algorithm.

In general, y is the geometric median if and only if there are vectors ui such that:

0=

m
\sum
i=1

ui

where for xi ≠ y,

ui=

xi-y
\left\|xi-y\right\|
and for xi = y,

\|ui\|\leq1.

An equivalent formulation of this condition is

\sum

1\lei\lem,xi\ney
xi-y
\left\|xi-y\right\|

\le\left|\{ i\mid1\lei\lem,xi=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.[5] Let

M

be a Riemannian manifold with corresponding distance function

d( ⋅ , ⋅ )

, let

w1,\ldots,wn

be

n

weights summing to 1, and let

x1,\ldots,xn

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\inM}{\operatorname{argmin}}

n
\sum
i=1

wid(x,xi)

.If all the weights are equal, we say simply that

m

is the geometric median.

See also

References

Notes and References

  1. Claim 18.10, Geometric Methods and Optimization Problems, V. Boltyanski, H. Martini, V. Soltan, Springer, 1999.
  2. , p. 6; . The convex case was originally proven by Giovanni Fagnano.
  3. . Earlier, proved that the Steiner point for 5 points in the plane cannot be constructed with ruler and compass
  4. ; .
  5. Robust statistics on Riemannian manifolds via the geometric median . Fletcher . P. Thomas . Venkatasubramanian . Suresh . Joshi . Sarang . 23 June 2008 . IEEE . 2008 IEEE Conference on Computer Vision and Pattern Recognition . Anchorage, AK, USA . IEEE Conference on Computer Vision and Pattern Recognition.

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Geometric median".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.