Solved – K-medians, formula to compute the median

Question

If you are running K-medians, and your distance metric is the L1 norm, how do you derive that the center of each centroid is the median of the data points assigned to it?

Second, how do you compute the geometric median?

Third, are there any implementations of k-medians algorithm?

Answer 1

The definition of the geometric median is that of the $L_1$ optimum.

There seem to be two common approximations in use:

• component-wise medians, optimizing each dimension independently
• medoids, taking only the data samples into account

It's not clear to me why the component-wise median is not the same as the geometric median.