Algorithm to compute "median"

Question

Let $x_1,\dots,x_m\in\mathbb{R}^d$ be a finite set of points. I define the $d$-dimensional "median" $y\in\mathbb{R}^d$ to be the point minimizing the sum of distances to $x_j$, $$ y = \arg\min_{z\in\mathbb{R}^d} \sum_{j=1}^m |z-x_j|. $$ (Note that the median might not exist, for example if $x_j$ lie on a straight line).

Is there an efficient algorithm to compute $y$? For example, when $m=3$ and $d=2$ there is a construction for the Fermat point of a triangle, which is what I am calling the median here.

Thanks!

Answer 1

You might be looking for Weiszfeld's algorithm, mentioned here.