Robusness of median

Question

If we let $X$ be a set of pints in $\mathrm{R}^2$, and let $g(X) = \arg \min_{y \in \mathrm{R}^2} \sum_{x_i \in X} \parallel x_i -y \parallel_2$ (geometric median of $X$). If $X$ and $X'$ are neighbours which means they differ in only one element, we denote this by $X \sim X'$, we want to compute $\sup_{X':X \sim X'} \parallel g(X)-g(X') \parallel_2$, could anyone give me some hints on how to start on this?

Answer 1

Here's a start:

The gradient of $\|x_i - y\|_2$ with respect to $y$ (if $y \ne x_i$) is the unit vector in the direction of $y - x_i$. At a minimum that is not one of the $x_i$, those unit vectors will add to $0$. The minimum might also be one of the $x_i$: if that happens, then the sum of the unit vectors for the other $x_i$ has norm $\le 1$.