Fact-checked by Grok 2 weeks ago

Geometric median

The geometric median of a finite set of points \{ \mathbf{x}_1, \dots, \mathbf{x}_n \} in Euclidean space \mathbb{R}^d is the point \mathbf{m} that minimizes the objective function \sum_{i=1}^n \| \mathbf{m} - \mathbf{x}_i \|_2, where \| \cdot \|_2 denotes the Euclidean norm.^[1] This definition extends the classical one-dimensional median, which minimizes the sum of absolute deviations, to multivariate settings without relying on inner products or assuming differentiability at the points themselves.^[1] Unlike the arithmetic mean, the geometric median exhibits high breakdown point robustness, remaining stable even when up to nearly half of the points are corrupted by arbitrary outliers, making it valuable for robust estimation in statistics and optimization.^[1] The origins of the geometric median trace back to the 17th century, when Pierre de Fermat posed the problem of finding a point minimizing the total distance to three given points in the plane, which he communicated to Evangelista Torricelli around 1644.^[2] Torricelli solved it in 1646 using a geometric construction: for a triangle with all angles less than 120 degrees, the solution is the point inside the triangle from which each side subtends an angle of 120 degrees, achievable by erecting outward equilateral triangles on the sides and connecting the new vertices to the opposite original vertices, whose intersection yields the point.^[2] If any angle is 120 degrees or more, the median coincides with the vertex of that angle.^[3] This special case for three points is known as the Fermat–Torricelli point, and the problem's generalization to n points or weighted distances became central to location theory.^[1] In 1909, Alfred Weber formalized the weighted version in his seminal work on industrial location, framing it as minimizing transportation costs to multiple demand points, thus linking the geometric median to economic geography and facility location problems.^[3] For the general case, no closed-form solution exists except in one dimension or when points are collinear, where it reduces to the standard median.^[1] The geometric median is unique provided the points are not collinear and the distribution is absolutely continuous, and it satisfies the first-order optimality condition \sum_{i=1}^n \frac{\mathbf{x}_i - \mathbf{m}}{\| \mathbf{x}_i - \mathbf{m} \|_2} = 0 (or a subgradient condition if \mathbf{m} coincides with a point).^[1] Computationally, it is often approximated via iterative procedures like the Weiszfeld algorithm, proposed in 1937, which updates the estimate as a weighted average \mathbf{m}^{(k+1)} = \frac{\sum_{i=1}^n \frac{\mathbf{x}_i}{\| \mathbf{x}_i - \mathbf{m}^{(k)} \|_2}}{\sum_{i=1}^n \frac{1}{\| \mathbf{x}_i - \mathbf{m}^{(k)} \|_2}}, converging linearly under mild conditions despite the objective's non-differentiability.^[4] Beyond classical geometry and location theory, the geometric median finds applications in robust multivariate analysis, such as median-of-means estimators for heavy-tailed distributions in high dimensions, where it achieves near-optimal rates for mean estimation under contamination models.^[1] It also appears in machine learning for tasks like robust aggregation in federated learning, image processing for feature alignment, and manifold learning on Riemannian spaces, where geodesic distances replace Euclidean ones.^[1] Recent algorithmic advances have enabled exact or approximate solutions in nearly linear time for fixed dimensions, facilitating its use in large-scale data settings.^[5]

Definition and History

Formal Definition

The geometric median of a finite set of points \{ \mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_n \} in \mathbb{R}^d, where each \mathbf{x}_i \in \mathbb{R}^d, is defined as the point \mathbf{y} \in \mathbb{R}^d that minimizes the sum of Euclidean distances to the given points:

\mathbf{y} = \arg \min_{\mathbf{z} \in \mathbb{R}^d} \sum_{i=1}^n \| \mathbf{x}_i - \mathbf{z} \|_2.

^[1]^[5] The objective function associated with this optimization problem is f(\mathbf{y}) = \sum_{i=1}^n \| \mathbf{x}_i - \mathbf{y} \|_2, which is convex as a sum of convex functions (each Euclidean norm is convex).^[1] However, f(\mathbf{y}) is non-smooth at the points \mathbf{y} = \mathbf{x}_i for i = 1, \dots, n, where the subgradient is not uniquely defined due to the non-differentiability of the norm.^[1]^[6] Unlike the arithmetic mean, which minimizes the sum of squared Euclidean distances \sum_{i=1}^n \| \mathbf{x}_i - \mathbf{y} \|_2^2 and is sensitive to outliers, the geometric median uses the L1-type objective based on unsquared distances, providing greater robustness to extreme values.^[1]^[7] It also differs from the component-wise (or coordinate-wise) median, which applies the univariate median separately to each dimension and lacks rotation invariance, whereas the geometric median respects the Euclidean geometry of the space.^[1]^[8] Geometrically, the geometric median can be interpreted as the optimal location for a facility that minimizes the total travel distance to a set of demand points in Euclidean space, a classic problem in location theory.^[5]

Historical Background

The origins of the geometric median trace back to the 17th century with the Fermat-Torricelli problem, posed by Pierre de Fermat in a letter to Evangelista Torricelli around 1644. This classical problem seeks to find a point in the plane that minimizes the total distance to three given points forming a triangle, provided all angles are less than 120 degrees. Torricelli solved it geometrically: construct outward equilateral triangles on each side of the original triangle and connect each new vertex to the opposite vertex of the original; these lines intersect at the minimizing point.^[2] In the early 20th century, the concept was generalized by Alfred Weber in his 1909 book Über den Standort der Industrien (translated as Theory of the Location of Industries), formulating what is now known as the Weber problem. Weber addressed facility location in industrial economics, aiming to minimize the weighted sum of distances from a single facility to multiple demand points, extending the unweighted case to account for varying transportation costs or weights. This formulation established the geometric median as a core element of location theory in operations research.^[9] The geometric median gained recognition in statistics during the mid-20th century as a robust multivariate measure of central tendency, often termed the spatial median. J. B. S. Haldane introduced it in 1948 as the point minimizing the sum of Euclidean distances to observations in a multivariate distribution, highlighting its role in location estimation. Subsequent work by B. M. Brown in 1983 further analyzed its properties, emphasizing its high breakdown point of approximately 50% against outliers, making it superior to the arithmetic mean for robust inference. By the 1990s, researchers explored its applications in robust statistical procedures under contamination. Early computational interest emerged with Endre Weiszfeld's 1937 iterative algorithm, which approximates the geometric median by fixed-point iterations weighted by inverse distances, providing an efficient method for the Weber problem and influencing later optimization techniques. The term "geometric median" became standardized in mathematical literature around this period, distinguishing it from statistical nomenclature while underscoring its geometric minimization nature.^[5]

Properties

Existence and Uniqueness

The geometric median of a finite set of points in Euclidean space always exists. The objective function defining the geometric median, f(\mathbf{y}) = \sum_{i=1}^n \|\mathbf{y} - \mathbf{x}_i\|, is continuous and convex as a nonnegative linear combination of convex functions, each of which is the composition of the convex Euclidean norm with an affine map. Moreover, f is coercive, satisfying f(\mathbf{y}) \to \infty as \|\mathbf{y}\| \to \infty, which guarantees the existence of at least one global minimizer by standard results in convex optimization.^[10] The set of geometric medians is convex and lies within the convex hull of the points \{\mathbf{x}_1, \dots, \mathbf{x}_n\}. To see this, suppose a minimizer \mathbf{y}^* lies outside the convex hull; then there exists a direction toward the hull along which the directional derivative of f is negative, contradicting minimality. This property holds in any normed space where the norm is strictly convex, such as the Euclidean norm.^[10] Uniqueness of the geometric median holds unless all points are collinear. When the points are not collinear, the objective function f is strictly convex, ensuring a unique minimizer; this follows from the positive definiteness of the Hessian \nabla^2 f(\mathbf{y}) = \sum_{i=1}^n \frac{1}{\|\mathbf{y} - \mathbf{x}_i\|} \left( I - \frac{(\mathbf{y} - \mathbf{x}_i)(\mathbf{y} - \mathbf{x}_i)^T}{\|\mathbf{y} - \mathbf{x}_i\|^2} \right) for \mathbf{y} not coinciding with any \mathbf{x}_i, which implies that f cannot be affine along any line segment. In the collinear case, the problem reduces to finding the one-dimensional median along the line spanned by the points, which is unique if n is odd but non-unique if n is even and the two central points differ, in which case any point on the line segment joining those central points achieves the minimum.^[11]^[10]

Robustness Characteristics

The geometric median exhibits strong robustness as a location estimator, particularly in the presence of outliers. A key measure of this robustness is its breakdown point, defined as the smallest fraction of contaminated observations that can cause the estimator to take on arbitrarily large values. For the geometric median in Euclidean space, this breakdown point is 0.5, meaning it can withstand up to 50% of the data points being outliers without failing, assuming the remaining points are not collinear.^[12] In contrast, the arithmetic mean has a breakdown point of 0, as even a single outlier can arbitrarily bias it.^[13] This high breakdown point makes the geometric median particularly suitable for datasets with gross errors or heavy-tailed distributions. The geometric median also demonstrates desirable equivariance properties under certain transformations. It is translation invariant, so shifting all data points by a fixed vector shifts the median by the same amount. Similarly, it is equivariant under orthogonal transformations such as rotations, preserving the geometric structure of the data. Additionally, it is scale invariant: uniformly scaling the data by a positive factor scales the median accordingly. However, it is not fully affine equivariant, as it does not preserve structure under general linear transformations like shearing.^[12] These properties ensure that the estimator behaves consistently under common data preprocessing steps that maintain Euclidean geometry. Under standard statistical assumptions, the geometric median is consistent and asymptotically normal for independent and identically distributed (i.i.d.) samples from distributions with finite first moments. Specifically, as the sample size n increases, the estimator converges almost surely to the true population geometric median, and \sqrt{n} times the centered estimator converges in distribution to a normal random vector with mean zero and a covariance matrix depending on the underlying distribution.^[14] For elliptically symmetric distributions like the multivariate normal, its asymptotic relative efficiency compared to the sample mean is $2/\pi \approx 0.637, indicating slightly lower precision in uncontaminated settings but superior performance under contamination models where outliers are present.^[15] Relative to other robust estimators, such as the minimum covariance determinant, the geometric median offers comparable breakdown robustness but often higher efficiency in moderate contamination scenarios due to its simplicity and direct minimization of sum of distances.^[16]

Special Cases

One-Dimensional Case

In the one-dimensional case, the geometric median of a finite set of points \{x_1, x_2, \dots, x_m\} on the real line coincides with the classical median of those points.^[1] This equivalence arises because the geometric median generalizes the standard median, which minimizes the sum of absolute deviations in one dimension.^[1] The objective function simplifies to

f(y) = \sum_{i=1}^m |x_i - y|,

which is minimized precisely at the median, providing an explicit closed-form solution without requiring iterative methods.^[17] To compute it, sort the points in non-decreasing order to obtain x_{(1)} \leq x_{(2)} \leq \dots \leq x_{(m)}. If m is odd, the geometric median is uniquely y = x_{((m+1)/2)}, the middle point.^[17] If m is even, any point y in the closed interval [x_{(m/2)}, x_{(m/2 + 1)}] minimizes the objective function, with the sum of deviations remaining constant across this interval.^[17] This sorting-based approach is efficient, with time complexity O(m \log m), and underscores the geometric median's role as the one-dimensional L1 median. For example, consider the points \{1, 2, 3, 100\}. Sorted, they are $1, 2, 3, 100, so m=4 is even and the geometric median is any y \in [2, 3]. The objective function evaluates to f(y) = 100 for y \in [2, 3], compared to f(1) = 102 or f(100) = 294, demonstrating how the median resists the outlier at 100 by placing the minimizer near the central cluster.^[17]

Planar Case

In the planar case, the geometric median of three non-collinear points forming a triangle is known as the Fermat-Torricelli point.^[19] If all interior angles of the triangle are less than 120 degrees, this point lies inside the triangle and is characterized by the property that the angles subtended by each pair of vertices at the point are exactly 120 degrees.^[19] In this configuration, the lines connecting the Fermat-Torricelli point to the vertices form 120-degree angles with each other.^[20] If one interior angle of the triangle is 120 degrees or greater, the Fermat-Torricelli point coincides with the vertex of that largest angle.^[20] This ensures the point minimizes the total distance sum, as moving away from the obtuse vertex would increase the distances to the other points without sufficiently reducing the distance to itself.^[2] One classical construction method for the Fermat-Torricelli point, when it lies inside the triangle, involves erecting outward equilateral triangles on two sides of the original triangle and drawing the circumcircles of these equilateral triangles; their intersection point (other than the shared vertex) is the Fermat-Torricelli point.^[19] An alternative construction draws lines from the new vertices of the equilateral triangles to the opposite vertices of the original triangle, with these lines (Torricelli lines) concurrent at the Fermat-Torricelli point.^[20] A proof of minimality leverages a variant of Viviani's theorem: by constructing an equilateral triangle on one side and considering the sum of perpendicular distances from the point to its sides, which equals the altitude, this equates to the total distance sum to the vertices.^[20] For four or more points in the plane, no closed-form expression exists for the geometric median in general, requiring approximate methods for computation.^[2] However, for four coplanar points, the geometric median coincides with their unique Radon point, the intersection of the diagonals in the convex quadrilateral formed by partitioning the points into two pairs whose convex hulls intersect.

Computation

Iterative Algorithms

One of the earliest and most widely used iterative methods for approximating the geometric median is Weiszfeld's algorithm, introduced in 1937 as a fixed-point iteration for solving the Fermat-Weber location problem.^[21] The algorithm proceeds by starting with an initial guess y_0 (often the arithmetic mean of the points) and iteratively updating the estimate according to the formula

y_{k+1} = \frac{\sum_{i=1}^n \frac{x_i}{\|x_i - y_k\|}}{\sum_{i=1}^n \frac{1}{\|x_i - y_k\|}},

where x_i are the input points in Euclidean space and \| \cdot \| denotes the Euclidean norm.^[21] This update can be interpreted as a weighted average of the points, with weights inversely proportional to their distances from the current estimate y_k. The iteration continues until convergence, typically measured by a small change in y_k or the objective function value. A key issue with the basic Weiszfeld iteration arises when y_k coincides with one of the sample points x_j, causing division by zero in the denominator. To address this, a modified version skips the contribution of that point in both numerator and denominator during the update, or alternatively projects the next iterate away from the coinciding point; this ensures the algorithm avoids stagnation and maintains progress toward the optimum.^[22] If the initial guess is exactly at a sample point and no other points coincide with it, the unmodified algorithm may fail to converge, but the modification resolves this by guaranteeing descent.^[22] Under the non-degeneracy assumption that the geometric median does not coincide with any sample point, Weiszfeld's algorithm exhibits linear convergence to the unique minimizer.^[23] The objective function being strictly convex (except in degenerate cases like collinearity) ensures that the limit point, if reached, is the global minimum. However, the algorithm can converge slowly when the current iterate is near a sample point, as the weights become unbalanced and the updates diminish in magnitude.^[22] Variants of Weiszfeld's algorithm extend its applicability, including a weighted version where each point x_i has an associated positive weight w_i, modifying the update to

y_{k+1} = \frac{\sum_{i=1}^n w_i \frac{x_i}{\|x_i - y_k\|}}{\sum_{i=1}^n w_i \frac{1}{\|x_i - y_k\|}}.

This handles the weighted geometric median while preserving similar convergence properties. Accelerated variants, such as Newton-type enhancements, improve the linear rate by incorporating second-order information, achieving superlinear convergence in practice without altering the core iterative structure. These modifications maintain the algorithm's simplicity and efficiency for moderate-dimensional problems.

Optimization Formulations

The geometric median of points x_1, \dots, x_n \in \mathbb{R}^d is defined as the point y \in \mathbb{R}^d that minimizes the convex objective function

f(y) = \sum_{i=1}^n \|y - x_i\|_2.

This formulation arises naturally in location theory and robust statistics as an \ell_1-type norm minimization problem over Euclidean distances. To enable efficient computation with conic solvers, the problem can be reformulated as a second-order cone program (SOCP) using the epigraph form:

\begin{align*} \min_{y, \{t_i\}} &\quad \sum_{i=1}^n t_i \\ \text{s.t.} &\quad \|y - x_i\|_2 \leq t_i, \quad \forall i = 1, \dots, n, \\ & t_i \geq 0, \quad \forall i = 1, \dots, n, \end{align*}

where each constraint defines a second-order cone in \mathbb{R}^{d+1}. This SOCP structure allows the use of interior-point methods or specialized conic solvers, with solvers like MOSEK or CVX handling instances up to moderate n and d efficiently.^[24] Since f(y) is convex but nonsmooth (except at points coinciding with data), subgradient descent methods are applicable. For y \neq x_i for all i, a subgradient is given by

\partial f(y) = \sum_{i=1}^n \frac{y - x_i}{\|y - x_i\|_2},

with the norm of any subgradient bounded by n to ensure descent directions exist away from the data points. Stochastic variants sample individual terms scaled by n to approximate this subgradient, enabling scalable implementations.^[25] Recent algorithmic advances have focused on faster approximate solutions. Cohen et al. (2016) introduced methods achieving \varepsilon-approximate geometric medians in nearly linear time O(nd \log^3(1/\varepsilon)) using matrix sketching to accelerate gradient computations and interior-point techniques, improving upon prior O(n^2 d) barriers for high dimensions. Extensions to privacy-preserving settings include differentially private algorithms for the geometric median, such as that by Haghifam (2024), which add calibrated noise while maintaining utility bounds under concentrated differential privacy, via polynomial-time methods. More recently, Yang (2025) developed a nearly-linear time (\varepsilon, \delta)-DP algorithm achieving \tilde{O}(nd + d/\alpha^2) runtime for \alpha-multiplicative approximation, improving on prior work. These developments leverage the convex structure for theoretical guarantees on convergence and privacy.^[25]^[26]^[27]

Characterizations

Variational Formulation

The geometric median of a set of points \{x_1, \dots, x_n\} \subset \mathbb{R}^d is characterized variationally as the minimizer y^* of the convex objective function

f(y) = \sum_{i=1}^n \|y - x_i\|_2,

where \| \cdot \|_2 denotes the Euclidean norm.^[1] Since f is convex and subdifferentiable everywhere, y^* satisfies the first-order optimality condition $0 \in \partial f(y^*), with \partial f the subdifferential of f.^[10] When y^* \neq x_i for all i, the function f is differentiable at y^*, and the condition is

\sum_{i=1}^n \frac{x_i - y^*}{\|x_i - y^*\|_2} = 0.

This equation states that the sum of the unit vectors pointing from y^* to each data point x_i equals zero.^[10] Geometrically, it implies a balance of directional pulls: the geometric median acts as an equilibrium point where the unit forces toward the data points cancel out, analogous to a vector sum in statics.^[1] In the degenerate case where y^* = x_j for some j, the subdifferential includes the unit ball in the dual space for the nondifferentiable term \|y - x_j\|_2, leading to the condition

\left\| \sum_{i \neq j} \frac{x_i - y^*}{\|x_i - y^*\|_2} \right\|_2 \leq 1.

This ensures that the vector sum of unit directions toward the other points does not exceed unit length, allowing y^* to remain optimal by "absorbing" the imbalance within the subdifferential ball.^[10]

Subdifferential Conditions

The subdifferential of f at a point y \in \mathbb{R}^d is given by

\partial f(y) = \left\{ \sum_{i: y \neq x_i} \frac{y - x_i}{\| y - x_i \|_2} + v \;\middle|\; v \in \sum_{i: y = x_i} B(0,1) \right\},

where B(0,1) is the closed unit ball centered at the origin. This follows from the fact that f is a sum of convex functions, so its subdifferential is the Minkowski sum of the individual subdifferentials, and the subdifferential of each Euclidean norm term \| y - x_i \|_2 is the singleton \{ (y - x_i)/\| y - x_i \|_2 \} when y \neq x_i and the unit ball B(0,1) when y = x_i. The point y^* is a minimizer if and only if $0 \in \partial f(y^*), which provides a first-order optimality condition in convex analysis. This inclusion holds when the vector sum of the normalized directions (y^* - x_i)/\| y^* - x_i \|_2 for y^* \neq x_i, augmented by any vector in the unit ball for terms where y^* = x_i, contains the zero vector. The subgradient mapping y \mapsto \partial f(y) is monotone, meaning that for any y_1, y_2 \in \mathbb{R}^d, g_1 \in \partial f(y_1), and g_2 \in \partial f(y_2), the inequality \langle g_1 - g_2, y_1 - y_2 \rangle \geq 0 is satisfied; this monotonicity implies that any point satisfying $0 \in \partial f(y) is a global minimizer of f. Uniqueness of the geometric median follows from strict monotonicity of the subgradient mapping, which occurs when the points \{x_i\} are not collinear (i.e., they span \mathbb{R}^d affinely). In this case, f is strictly convex, ensuring a unique minimizer. If the points are collinear, the subdifferential condition may hold along a segment, leading to non-uniqueness. This subdifferential characterization connects to proximal operators in nonsmooth optimization, where the resolvent (I + \lambda \partial f)^{-1} (the proximal operator of f/\lambda) encodes subgradient information and enables algorithms like the proximal point method to converge to the geometric median by iteratively solving inclusions involving \partial f.^[28]

Generalizations

Weighted Versions

The weighted geometric median generalizes the unweighted case by assigning positive weights w_i > 0 to each data point x_i \in \mathbb{R}^d, often normalized such that \sum_{i=1}^m w_i = 1. It is defined as the point y that minimizes the objective function

f(y) = \sum_{i=1}^m w_i \|x_i - y\|_2,

where \|\cdot\|_2 denotes the Euclidean norm. This formulation arises naturally in scenarios where points have varying importance or "demand," such as in facility location problems. The function f(y) is convex, as it comprises a nonnegative linear combination of convex distance functions, ensuring that local minima are global and enabling the use of standard convex optimization techniques. Moreover, the minimizer is unique whenever the weighted points are not collinear in \mathbb{R}^d, a property that holds due to the strict convexity of f(y) under this condition. When all weights are equal (w_i = 1/m), the weighted geometric median coincides with the unweighted version. This weighted objective is classically known as the Weber problem, originally posed in the context of optimal industrial location to minimize total weighted transportation costs to demand points. A prominent iterative method for its computation is the weighted Weiszfeld algorithm, introduced in the seminal work by Weiszfeld. The update rule is given by

y_{k+1} = \frac{\sum_{i=1}^m w_i x_i / \|x_i - y_k\|_2}{\sum_{i=1}^m w_i / \|x_i - y_k\|_2},

provided y_k \neq x_i for all i; this fixed-point iteration converges to the unique minimizer under the non-collinearity assumption.

Extensions to Non-Euclidean Spaces

The geometric median generalizes to arbitrary metric spaces through the Fréchet median, defined as the point y that minimizes the sum of distances to the given points, y = \arg\min_{z} \sum_{i=1}^n d(x_i, z), where d denotes the metric.^[29] This formulation preserves the robustness properties of the Euclidean case, serving as a central tendency estimator with a breakdown point of 0.5, provided the points do not concentrate on a geodesic.^[12] In proper metric spaces, the empirical Fréchet median converges almost surely to the population median under uniform convergence of first-moment functions.^[29] On Riemannian manifolds, the geometric median employs geodesic distances in place of Euclidean norms, again minimizing \sum_{i=1}^n d_g(x_i, y), where d_g is the geodesic metric induced by the manifold's geometry.^[30] This extension applies to spaces like the sphere S^2, where it estimates central orientations from directional data such as 3D rotations represented as unit quaternions, or the manifold of symmetric positive-definite (SPD) matrices \mathrm{PD}(3), useful for robust averaging of diffusion tensors in medical imaging.^[30] Computation often leverages the Riemannian exponential map \Exp_y to update estimates via gradient descent on the objective, with the subgradient of the distance term given by -\Log_y(x_i) / \|\Log_y(x_i)\|, where \Log_y is the logarithm map.^[30] Consistency holds in compact Riemannian manifolds for generic data distributions with positive density.^[29] In high dimensions, the geometric median exhibits behavior approaching that of the arithmetic mean under conditions of weak dependence among coordinates, with the distance between the two vanishing asymptotically as dimension increases.^[31] Recent analysis provides an upper bound on this distance that decreases with dimensionality, alongside a first-order expansion confirming the median's alignment with the mean for distributions satisfying suitable tail and dependence assumptions.^[31] However, challenges persist due to the curse of dimensionality, which amplifies sensitivity to outliers and complicates convergence in sparse high-dimensional settings. Extensions to other spaces include graphs, treated as metric spaces under distances like the Hamming metric on adjacency matrices or spectral distances capturing global structure; the Fréchet median then minimizes the expected distance to a set of observed graphs, often computed by thresholding the expected adjacency matrix for Hamming cases.^[32] In Hilbert spaces, such as separable infinite-dimensional spaces like L^2([0,1]), the geometric median minimizes \mathbb{E}[\|X - u\| - \|X\|] and admits consistent estimators via averaged stochastic gradient methods, achieving L^2 convergence rates of O(\log n / n^\alpha) for \alpha \in (1/2, 1) and asymptotic normality under mixing conditions.^[12] In infinite dimensions, approximate geometric medians maintain strong consistency and asymptotic normality, improving prior bounds even for exact medians in Hilbert spaces.^[33]

Applications

Location Theory

In location theory, the geometric median addresses the challenge of optimally placing a single facility to serve multiple demand points while minimizing total transportation costs. This is exemplified by the Weber problem, which seeks the site that minimizes the sum of weighted distances to demand points, where weights reflect demand volumes or priorities and distances represent transport costs.^[34] Formulated by Alfred Weber in his seminal 1909 work Theory of the Location of Industries, the problem modeled industrial site selection by balancing material sourcing and market proximity, influencing early operations research on economic geography. The solution corresponds to the weighted geometric median, a direct generalization of the unweighted case.^[34] Practical applications of the geometric median in the Weber problem include warehouse placement to reduce logistics expenses across supply chains and emergency service facility siting to shorten average response distances in urban areas. These optimizations ensure efficient resource allocation, such as positioning distribution centers near clustered customer sites or locating fire stations to cover high-risk zones. For scenarios involving multiple facilities, the single-facility geometric median ties into the broader p-median problem, which extends the objective to p sites minimizing aggregate distances to the nearest facility, often solved via heuristics building on median principles. Continuous variants of the Weber problem adapt the geometric median to scenarios where demand is distributed over regions rather than discrete points, requiring minimization of the integral of distances weighted by regional density.^[35] Key advancements include exact algorithms for computing the continuous 1-median in polygonal domains, such as simple polygons under L1 geodesic distances, solvable in linear time relative to the number of vertices.^[35] These results, from studies around 2003, enable precise facility placement in areas like linear demand corridors modeled as polygonal chains, enhancing models for elongated service territories.^[35]

Statistics and Machine Learning

In statistics, the geometric median serves as a robust estimator for the central tendency of multivariate data, particularly in the presence of outliers or heavy-tailed distributions. A key application is in robust mean estimation through the geometric median-of-means (GMOM) procedure, where the data is partitioned into subsamples, the arithmetic mean is computed for each, and the geometric median is then taken over these means. This approach achieves near-optimal error rates under contamination models, with statistical error bounds improving on prior constructions for heavy-tailed distributions in Euclidean spaces. For instance, under sub-Gaussian assumptions with up to εn contamination, the GMOM estimator converges at a rate of O(√(d log n / n) + ε √d), where d is the dimension and n the sample size, providing resistance to adversarial outliers.^[36] In machine learning, the geometric median facilitates robust aggregation in federated learning settings, where client updates may be noisy or malicious. Algorithms like Robust Federated Aggregation (RFA) employ the geometric median to combine model parameters from distributed clients, mitigating Byzantine faults and achieving convergence rates comparable to non-robust methods under bounded heterogeneity. This aggregation is particularly strategyproof, meaning individual clients cannot significantly manipulate the global model by misreporting their updates, as quantified by approximation guarantees in high-dimensional spaces. Recent extensions integrate it with alternating minimization for Byzantine-robust federated learning, ensuring resilience against up to f < n/2 faulty clients while maintaining linear speedup in communication rounds.^[37]^[38] For privacy-preserving computation, differentially private (DP) algorithms for the geometric median enable estimation with bounded leakage of individual data points. These methods, such as exponential mechanism-based sampling or optimization over smoothed objectives, achieve ε-DP while preserving the O(√(d/n)) non-private rate up to logarithmic factors. Advances in 2024-2025 have yielded nearly-linear time algorithms, running in Õ(nd) time for n points in d dimensions, by leveraging stochastic gradient descent on convex relaxations or private iterative solvers, making it feasible for large-scale robust location estimation in sensitive datasets like medical imaging.^[39]^[27] In ultrahigh-dimensional inference, the geometric median (often termed spatial median) supports asymptotic analysis of location parameters when d ≫ n. Under elliptical distributions, the sample spatial median admits a Bahadur representation with Gaussian limits after debiasing, enabling valid confidence regions and hypothesis tests for the mean vector via maximum-norm bounds on the remainder. For d up to exp(o(√n)), the estimator's asymptotic normality holds with rate √n, facilitating inference in genomics or signal processing where traditional means fail due to sparsity or outliers.^[40] Beyond core estimation, the geometric median aids change detection in remote sensing by compositing multispectral time series into cloud-free images. The Digital Earth Australia (DEA) Geometric Median product processes Landsat observations to generate annual pixel composites, minimizing spectral distortions from atmospheric effects or sensor noise, which supports monitoring land cover changes like deforestation or urban growth across vast areas. This method preserves inter-band correlations in high-dimensional data, outperforming linear averages in robustness to transient anomalies.^[41]

References

[1]
[PDF] The Geometric Median and Applications to Robust Mean Estimation
Jul 19, 2023 · This paper is devoted to the statistical and numerical properties of the geometric median, and its applications to the problem of robust mean ...
[2]
[PDF] The Fermat-Torricelli Point and Cauchy's Method of Gradient Descent
1.2 Torricelli's 3-point Geometric Median Solution. Torricelli, working in the mid 1600s, did not yet have the well-developed calculus toolbox that would.
[3]
[PDF] SOLVING THE FERMAT-WEBER PROBLEM A NUMERICAL AND ...
A generalization of the original problem leads to a geometric median – the problem of minimizing the sum of weighted distances. Finding a geometric median ...
[4]
(PDF) Weiszfeld's Method: Old and New Results - ResearchGate
Aug 6, 2025 · In this paper, we review both the past and the ongoing research on Weiszfed's method. The existing results are presented in a self-contained and concise manner.
[5]
[PDF] Geometric Median in Nearly Linear Time
Abstract. In this paper we provide faster algorithms for solving the geometric median problem: given n points in Rd compute a point that minimizes the sum ...
[6]
[PDF] Solving Non-smooth Constrained Programs with Lower Complexity ...
The geometric median problem, also known as the Fermat-Weber problem ... which is a non-smooth convex optimization problem. It can be shown that the ...
[7]
[PDF] Geometric Median Matching for Robust k-Subset Selection ... - arXiv
Apr 3, 2025 · Our key idea is to replace the empirical mean with a robust surrogate – Geometric Median ... sum of squared distances. On the other hand, the ...
[8]
Is the coordinate-wise median equal to the geometric median if we ...
Sep 24, 2021 · One natural way is to compute the coordinate-wise median, but this is not rotation-invariant. The coordinate-wise median is equivalent to ...How can I find the geometric median of n points in 2D Euclidean ...Sensitivity of geometric median to moving one pointMore results from math.stackexchange.com
[9]
Exact and Approximate Solutions to the Multisource Weber Problem ...
Weber, A., Über den Standort der Industrien Tübingen (1909). Translated as: 'Alfred Weber's Theory of the Location of Industries' (University of Chicago ...<|control11|><|separator|>
[10]
The multivariate L1-median and associated data depth - PNAS
In statistics, the solution of this optimization problem is the spatial median or L1-MM, considered by Brown (3) and. Small (4). As noted by Kuhn (5), the ...<|control11|><|separator|>
[11]
Geometric median and robust estimation in Banach spaces
to the convex hull of {x1,...,xk}. Indeed, if x∗ coincides with one of xj 's, there is nothing to prove. Otherwise, since for any v ∈ H we have DF(x∗;v) ...
[12]
Robust Approaches to Computing the Geometric Median and ...
Feb 24, 2016 · 1, a proof of uniqueness of the geometric median is provided here ... collinear, uniqueness of the solution μ follows from strict.
[13]
Efficient and fast estimation of the geometric median in Hilbert ...
In this paper, we explore another direction. The geometric median, defined as the minimizer of a simple functional that is differentiable everywhere when the ...
[14]
Breakdown Point - an overview | ScienceDirect Topics
As was mentioned earlier, the estimator of a sample mean is not robust and has a breakdown point of 0%. As the sample mean is used in calculating the sample ...
[15]
Efficient and fast estimation of the geometric median in Hilbert ...
Jan 22, 2011 · We focus here on the estimation of the geometric median which is a direct generalization of the real median and has nice robustness properties.
[16]
The asymptotic efficiency of the spatial median for elliptically ...
Mar 15, 2012 · A detailed study of the asymptotic efficiency of the spatial median under elliptically symmetric distributions is presented.
[17]
Statistical Uses of the Spatial Median - 1983 - Wiley Online Library
The spatial median, called the mediancentre in an earlier paper by J. C. ... its asymptotic efficiency relative to the sample mean vector with normal ...
[18]
[PDF] A Simple Noncalculus Proof That the Median Minimizes the Sum of ...
It is widely known among statisticians that the median minimizes the sum of the absolute deviation about any point for a set of x's, xl, x2, x3, . . . , x,.
[19]
Fermat Points -- from Wolfram MathWorld
The first Fermat point can be constructed by drawing equilateral triangles on the outside of the given triangle and connecting opposite vertices. The three ...
[20]
[PDF] On the Fermat point of a triangle - Optimization Online
Jan 26, 2017 · Based on geometrical arguments this problem was first solved by Torricelli shortly after, by Simpson in 1750, and by several others.Missing: primary | Show results with:primary
[21]
On the point for which the sum of the distances to n given points is ...
... (1937) pp. 355–386 is published. Translation with annotations of E. Weiszfeld ... paper of Weiszfeld. Boxed numerals are references to observations about the ...
[22]
On the Convergence of a Class of Iterative Methods for Solving the ...
The best-known algorithm for solving the location problem is an iterative scheme devised by Weiszfeld in 1937. ... Ostresh, Jr., (1978) On the Convergence of a ...
[23]
Linear convergence of generalized Weiszfeld's method | Computing
Weiszfeld's method is widely used for solving problems of optimal location. It is shown that a very general variant of this method converges linearly.
[24]
[PDF] MOSEK Modeling Cookbook
The geometric median of a sequence of points x1,...,xk ∈ Rn is defined as ... Second-order cone programming. Math. Pro- gramming, 95(1):3–51, 2003 ...
[25]
[1606.05225] Geometric Median in Nearly Linear Time - arXiv
Jun 16, 2016 · In this paper we provide faster algorithms for solving the geometric median problem: given n points in \mathbb{R}^{d} compute a point that minimizes the sum of ...
[26]
[2406.07407] Private Geometric Median - arXiv
Jun 11, 2024 · In this paper, we study differentially private (DP) algorithms for computing the geometric median (GM) of a dataset.Missing: differential | Show results with:differential
[27]
[PDF] Proximal Algorithms - Stanford University
This suggests a close connection between proximal operators and gradient methods, and also hints that the proximal operator may be useful in optimization.
[28]
[PDF] Some properties of Fréchet medians in Riemannian manifolds - HAL
Dec 2, 2011 · The consistency of Fréchet medians is proved for probabil- ity measures in proper metric spaces. In the context of Riemannian manifolds, ...
[29]
https://hal.science/hal-00633203v2/document
[30]
On the distance between mean and geometric median in ... - arXiv
Aug 18, 2025 · The geometric median, a notion of center for multivariate distributions, has gained recent attention in robust statistics and machine learning.Missing: behavior | Show results with:behavior
[31]
https://arxiv.org/abs/2508.12926
[32]
Statistical properties of approximate geometric quantiles in infinite ...
Oct 31, 2022 · Our consistency and asymptotic normality results significantly improve the state of the art, even for exact geometric medians in Hilbert spaces.
[33]
On the Complexity of Some Common Geometric Location Problems
The p-center problem minimizes max distance from demand to supply points, and the p-median problem minimizes the sum of distances from demand to supply points. ...
[34]
[cs/0310027] On the continuous Fermat-Weber problem - arXiv
Oct 15, 2003 · Abstract: We give the first exact algorithmic study of facility location problems that deal with finding a median for a continuum of demand ...
[35]
The Geometric Median and Applications to Robust Mean Estimation
Jul 6, 2023 · This paper is devoted to the statistical and numerical properties of the geometric median, and its applications to the problem of robust mean estimation.Missing: contamination | Show results with:contamination
[36]
[PDF] On the Strategyproofness of the Geometric Median - HAL
Apr 17, 2024 · ... definition of the geometric median coincides with the definition of the median. As a result, the geometric median may not be uniquely defined.
[37]
Byzantine-Robust Aggregation for Federated Learning with ...
Aug 31, 2024 · This approach employs geometric median as a robust aggregation method and integrates federated learning parameters and historical processes ...
[38]
[PDF] Private Geometric Median - NIPS papers
It is known that the GM is inside the convex hull of the datapoints. However, this convex hull can have a very large diameter due to a small number of ...
[39]
[2505.20189] Private Geometric Median in Nearly-Linear Time - arXiv
Estimating the geometric median of a dataset is a robust counterpart to mean estimation, and is a fundamental problem in computational geometry.Missing: differential | Show results with:differential
[40]
Statistical Inference for Ultrahigh Dimensional Location Parameter ...
Jan 9, 2023 · This paper studies statistical inference for ultrahigh dimensionality location parameter based on the sample spatial median under a general multivariate model.Missing: asymptotic | Show results with:asymptotic