Geometric median

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 minimizer of the sum of the L2 distances: :\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 p1, ..., pn, 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}.) • The geometric median is unique whenever the points are not collinear. • The geometric median is equivariant for Euclidean similarity transformations, including translation 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. 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. ==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. 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, 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. ==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 = \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 ui such that: :0 = \sum_{i=1}^m u_i where for xi ≠ y, :u_i = \frac {x_i - y} {\left \| x_i - y \right \|} and for xi = y, :\| u_i \| \leq 1 . An equivalent formulation of this condition is :\sum _{1\le i\le m, x_i\ne y} \frac {x_i - y} {\left \| x_i - y \right \|} \le \left|\{ \,i\mid 1\le i\le 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. Let M be a Riemannian manifold with corresponding distance function d(\cdot, \cdot), let w_1, \ldots, w_n be n non-negative weights, 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 any solution of : 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. == See also ==