Introduction

The geometric median is a central point in a spatial dataset that minimizes the sum of Euclidean distances to all points in the set. Unlike the arithmetic mean, the geometric median is less sensitive to outliers, making it particularly useful in applications such as facility location, robust statistics, and machine learning.

Definition and Mathematical Formulation

The geometric median $M$ of a set of points $X = \{ x_1, x_2, ..., x_n \}$ in $\mathbb\{R\}^d$ is defined as the point $M \in \mathbb{R}^d$ that minimizes the following objective function:

$$M = \operatorname{argmin}*{y \in \mathbb{R}^d} \sum*{i=1}^n | y - x\_i |$$

where $\| y - x_i \|$ represents the Euclidean distance between the point $y$ and point $x_i$.

Properties

• Uniqueness: The geometric median is unique unless all the data points lie on a line, in which case the median is not unique. • Robustness: It is less influenced by extreme values compared to the arithmetic mean. • Dimensionality: The geometric median is defined over any-dimensional Euclidean space.

Algorithms for Finding the Geometric Median

Finding the geometric median is generally more computationally challenging than finding the arithmetic mean. Here are several methods to approximate or compute the geometric median:

1. Weiszfeld's Algorithm

Weiszfeld's algorithm is a popular iterative method for finding the geometric median. It works as follows:

• Initialization: Start with an initial guess $m^{(0)}$, often the arithmetic mean or one of the points from the dataset. • Iteration: Update the estimate using:

$$m^{(k+1)} = \frac{\sum\_{i=1}^n \frac{x\_i}{| m^{(k)} - x\_i |}}{\sum\_{i=1}^n \frac{1}{| m^{(k)} - x\_i |}}$$

• Convergence: Repeat until convergence, which can be defined based on a small change between successive iterations.

Example: Consider three points in $\mathbb{R}^2$: $A = (1, 3)$, $B = (4, 5)$, $C = (7, 2)$. Using Weiszfeld’s algorithm starting with the arithmetic mean as the initial point, you iterate until convergence to find the geometric median.

2. Gradient Descent

The geometric median problem can also be approached using gradient descent by iteratively updating the coordinates in the direction that reduces the total distance:

1. Objective: Minimize $f(y) = \sum_{i=1}^n \| y - x_i \|$.
2. Gradient Calculation: The subgradient of $f(y)$ at $y$ is given by:

$$\nabla f(y) = \sum\_{i=1}^n \frac{y - x\_i}{| y - x\_i |}$$

1. Update Rule: Use a learning rate $\alpha$ to update $y$:

$$y^{(k+1)} = y^{(k)} - \alpha \nabla f(y^{(k)})$$

1. Convergence: Adjust the learning rate to ensure convergence.

3. Randomized Algorithms

Randomized algorithms can also be employed, particularly in high-dimensional spaces where deterministic algorithms become inefficient. They typically involve random sampling and expectation maximization techniques to approximate the median.

Applications

• Facility Location: The geometric median can determine the optimal location of a point to minimize transportation costs. • Robust Statistics: Used as a robust estimator of central tendency. • Machine Learning: Enhances k-median clustering, providing a robust alternative to k-means.

Comparison Table

Conclusion

The geometric median is a fundamental concept in multivariate data analysis, providing a robust measure of central tendency across various domains. Several computational approaches, each with its strengths and limitations, allow for its effective computation. Understanding these methods provides the flexibility to handle diverse datasets and requirements efficiently.

Further Reading

For additional details, delve into resources specifically focusing on algorithmic optimizations for the geometric median, such as academic papers and textbooks on advanced statistics and machine learning.