Definition

给定欧式空间中的$m$个点$x_i,x_2,...x_m (x_i \in \mathbb{R}^n)$，geometric median就是到这$m$个点的欧式距离和最小的点，即：

\[ \underset{y \in \mathbb{R}^n}{\operatorname{arg\,min}} \sum_{i=1}^m \left \| x_i-y \right \|. \]

其中的$y$就是所要求的geometry median.

Computation

令：

\[ f=\sum_{i=1}^m \left \| x_i-y \right \|, \]

将$f$对$y$求导，得：

\[ \frac{df}{dy}=\sum_{i=1}^m{\frac{(x_i-y)}{\|x_i-y\|}}. \]

由于从一个点到$y$的距离函数是一个凸函数，而$m$个凸函数的和仍然为凸，因此函数$f$为凸函数，而且有且只有一个最优解。为了找到这个最优值，我们令$\frac{df}{dy}=0$，得：

\[ \left. y=\biggl( \sum_{i=1}^n \frac{x_i}{\| x_i - y_j \|} \biggr) \right/ \biggl( \sum_{i=1}^n \frac{1}{\| x_i - y_j \|} \biggr). \]

上式没有直接的公式解，因此Endre Weiszfeld提出采用迭代逼近的方法来求解，即Weiszfeld算法。该算法先初始化（如随机生成）一个点$y_0$且保证$y_0$不与任何输入的点$x_i$相同；接着，采用下面的迭代式子来逼近最优解：

\[ \left. y_{j+1}=\biggl( \sum_{i=1}^m \frac{x_i}{\| x_i - y_j \|} \biggr) \right/ \biggl( \sum_{i=1}^m \frac{1}{\| x_i - y_j \|} \biggr) \]

该算法可以扩展到带权值的情况，即:

\[ \underset{y \in \mathbb{R}^n}{\operatorname{arg\,min}} \sum_{i=1}^m w_i \left \| x_i-y \right \|. \]

此时，$y_{j+1}$为：

\[ \left. y_{j+1}=\biggl( \sum_{i=1}^m \frac{w_i x_i}{\| x_i - y_j \|} \biggr) \right/ \biggl( \sum_{i=1}^m \frac{w_i}{\| x_i - y_j \|} \biggr). \]

Application

geometry median可以被用于点云的曲面重建和骨架提取中，具体可以参考如下论文：

1. Lipman Y, Cohen-Or D, Levin D, et al. Parameterization-free projection for geometry reconstruction[C]. ACM Transactions on Graphics (TOG). ACM, 2007, 26(3): 22.
2. Huang H, Wu S, Cohen-Or D, et al. L1-medial skeleton of point cloud[J]. ACM Trans. Graph., 2013, 32(4): 65.

Geometric median