Weiszfield algorithm

Geomtric median

The geometric median of a discrete point set in a Euclidean space is the point minimizing the sum of the Euclidean distances to the sample points. Given a set of point \(\{\rvx_i\}_{i=0}^{m}\) with each \(\rvx_i\in\sR^n\), the geometric median is defined as the sum of the L2 distances minimizer:

\[ \arg\min_{\rvp\in\sR^n}\sum_{i=0}^{m}\|\rvp -\rvx_i\|^2 \]

The geometric mean, i.e., centroid or center of mass, defined similarly to the geometric median as minimizing the sum of the squared L2 distances to each point. It can be easily obtained via averaging the coordinates of all points. However, the geometric median does not have a closed-form solution and requires iterative optimization.

Why no closed-form solution?

The objective function of the geometric median is non-quadratic. It is non-differentiable when \(\rvp = \rvx_i\). Thus, we need to use iterative optimization methods to find the solution.

Weiszfeld algorithm

The Weiszfeld algorithm is an iterative method to find the geometric median. 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:

\[ \rvp_{k+1} = \frac{\sum_{i=0}^{m}\frac{\rvx_i}{\|\rvp_k - \rvx_i\|}}{\sum_{i=0}^{m}\frac{1}{\|\rvp_k - \rvx_i\|}} \]

This update can be thought of as a weighted average of the sample points, where the weights are inversely proportional to the distances from the current estimate to the sample points. For initialization, we can use geometric mean.