How to Learn Weiszfeld’s Algorithm: Geometric Medians, Inverse-Distance Reweighting, Robust Location and Fermat–Weber Optimization

Wait, What?

The average point can be dragged far away by one extreme outlier; the geometric median resists that pull.

Weiszfeld’s algorithm computes the geometric median of a set of points: the point that minimizes the sum of Euclidean distances to them. The method repeatedly forms an inverse-distance weighted average, giving nearby observations more influence on the next iterate than distant ones. It is a classic algorithm connecting geometry, robust statistics, facility location and iterative optimization.

Quick Answer

Learn Weiszfeld through mean versus median → Fermat–Weber objective → geometric median → inverse-distance weights → fixed-point iteration → singular cases → modified Weiszfeld → convergence → weighted variants → robust applications → implementation and diagnostics. The professional skill is understanding both why the update works and why a naive implementation can fail when an iterate lands exactly on a data point.

1. Define the Geometric Median

Given points x₁,…,xₙ in ℝᵈ, the geometric median minimizes

F(y) = Σ ||y - x_i||_2

This differs from the arithmetic mean, which minimizes the sum of squared Euclidean distances. Squaring makes large residuals disproportionately influential; the unsquared distance objective is more robust to extreme points.

In one dimension, the geometric median reduces to the ordinary median. In two or more dimensions there is generally no coordinate-by-coordinate shortcut because Euclidean distance couples the coordinates.

2. The Fermat–Weber Interpretation

The same objective appears in facility location. If xᵢ are customer locations and travel cost is proportional to straight-line distance, a geometric median minimizes total distance to the facility. With positive weights wᵢ representing demand, the weighted objective becomes

F(y) = Σ w_i ||y - x_i||_2

This is the classical Fermat–Weber location problem.

3. Derive the Weiszfeld Update

Away from the data points, the gradient of the unweighted objective is

∇F(y) = Σ (y - x_i) / ||y - x_i||

At an optimum that is not itself one of the observations, set the gradient to zero and rearrange:

y = [Σ x_i / ||y - x_i||] / [Σ 1 / ||y - x_i||]

Weiszfeld turns this fixed-point relation into an iteration. Given the current yᵏ, compute inverse-distance weights and use their weighted average as yᵏ⁺¹.

4. Trace a Simple Example

Consider four points near the origin and one outlier far to the right:

(0,0), (0,2), (2,0), (2,2), (20,1)

The arithmetic mean is pulled strongly toward x=20. Start Weiszfeld from the mean and calculate distances to each point. The four nearby points receive relatively large inverse-distance weights; the far outlier receives a much smaller one. The next iterate moves back toward the dense cluster. Repeating the process converges toward the geometric median.

This makes robustness visible: the outlier still matters, but its leverage is proportional to distance rather than squared distance.

5. Weighted Weiszfeld

For positive weights wᵢ, use

alpha_i = w_i / ||y - x_i||
y_next = Σ alpha_i x_i / Σ alpha_i

A high-demand point can therefore exert more influence while the inverse-distance mechanism still tempers the effect of remoteness.

6. The Singularity Problem

The formula divides by ||y−xᵢ||. If the current iterate equals one of the data points, the naive update divides by zero. This is not a minor programming inconvenience; it reflects the fact that the Euclidean norm is not differentiable at zero.

Early presentations often assumed the iterate never lands exactly on an observation. Later work, including Vardi and Zhang, developed modified Weiszfeld procedures that handle these singular cases and preserve monotone convergence properties.

7. A Practical Modified Rule

A production implementation should detect when the iterate is equal or extremely close to a data point. One robust strategy is to use a modified Weiszfeld step based on the contribution of all other points and the subgradient condition at the coincident point, rather than inserting an arbitrary epsilon into the denominator and hoping for the best.

The important learning point is that singularity handling belongs to the mathematical algorithm, not merely to defensive coding.

8. Stopping Criteria

Useful stopping tests include:

• ||yᵏ⁺¹−yᵏ|| below a tolerance;
• relative reduction in F(y) below a tolerance;
• subgradient residual small enough for the application;
• maximum iteration limit as a safety guard.

Do not stop only because the iteration count “looks large enough.” Measure the optimization contract.

9. Complexity

For n points in d dimensions, one straightforward iteration computes n distances and one weighted sum, costing O(nd). Total cost is O(ndT) for T iterations. In large high-dimensional problems, memory layout, vectorization, batching and convergence rate become as important as the asymptotic expression.

10. Robustness: Mean, Coordinate Median and Geometric Median

The arithmetic mean is computationally cheap but sensitive to outliers. The coordinate-wise median is robust but depends on the coordinate system and does not minimize total Euclidean distance. The geometric median is rotation-equivariant and has strong robustness properties, which is why it appears in robust aggregation and median-of-means methods.

No estimator is universally best. If the data are well-modelled by Gaussian noise and efficiency near the mean is the main goal, the mean may be appropriate. If contamination or adversarial extremes matter, the geometric median can be much more stable.

11. Current Research Context

Modern work continues to study geometric medians for robust mean estimation, high-dimensional statistics and non-Euclidean spaces. Recent SIAM research analyses statistical and numerical properties of geometric medians, while contemporary optimization reviews revisit Weiszfeld’s convergence and modifications. The algorithm therefore remains a living tool rather than a historical curiosity.

12. Learn It With Prediction and Geometry

Start with a plotted point cloud. Before computing, ask where the mean will move when an outlier is added and where the geometric median should move. Then trace one Weiszfeld iteration by hand: distances, inverse-distance weights, weighted numerator, denominator and next point. Only after the geometry is visible should the learner implement a vectorized version.

PRIMM-style prediction and investigation, subgoal-labelled worked examples, and code-reconstruction scaffolds fit this algorithm well because each iteration has a small number of stable conceptual jobs.

13. Test It Properly

• One-dimensional inputs should agree with an ordinary median.
• Symmetric point sets should return the symmetry centre.
• Add a distant outlier and compare displacement of mean versus geometric median.
• Test a starting point equal to a data point.
• Test duplicate observations and nonuniform weights.
• Verify that the objective F(y) does not increase under the chosen modified method.
• Compare against a trusted geometric-median implementation on random small datasets.

Common Failure States

• Using squared distances and accidentally computing a mean-like objective.
• Forgetting inverse distance in the weights.
• Ignoring the zero-distance singularity.
• Adding an arbitrary epsilon without understanding how it changes the method.
• Stopping based only on iteration count.
• Confusing the geometric median with the medoid, which must be one of the observed points.
• Assuming robustness means complete immunity to adversarial or pathological data.

Practice Ladder

• Beginner: compare mean and median in one dimension.
• Foundation: trace Weiszfeld on three or four 2D points.
• Intermediate: implement weighted Weiszfeld with convergence diagnostics.
• Advanced: add mathematically correct singular-point handling and verify monotone objective decrease.
• Professional: compare mean, coordinate median, medoid and geometric median under increasing contamination, dimensionality and dataset size.

Learning Hall Boundary

This article owns Weiszfeld as an iterative geometric-median/Fermat–Weber algorithm. It does not replace k-means, clustering, generic convex optimization or graph-layout articles, and it does not touch MindOS, Bolt, Student/Studying Interface or private learner-model machinery.

Evidence Boundary

Endre Weiszfeld introduced the iterative method in 1937. Kuhn later established important convergence results, while Vardi and Zhang developed modified procedures addressing singular cases and monotone convergence. Their 2000 PNAS work on the multivariate L1 median and subsequent 2001 Mathematical Programming paper remain key references. Modern SIAM work continues to study geometric medians in robust mean estimation. The teaching progression draws on PRIMM, worked examples and scaffolded programming research.

Professional rule: you understand Weiszfeld when you can derive the fixed-point update, explain its robustness relative to the mean, handle coincidence with a data point correctly and justify stopping using the objective rather than habit.