Robustness of Geometric Median to Change of k Points

30 Views Asked by At

Let $N \in \mathbb{N}$ be a constant. Let $B_d(1)$ denote the ball of radius one in $\mathbb{R}^d$. Let $(a_1,\dots,a_N)\in (B_d(1))^N$ and $(b_1,\dots,b_N)\in (B_d(1))^N$ be two sets of N data points that differ in at most $1 \leq k<N$ points. In particular, $a_i=b_i$ for $i=\{1,\dots,n-k\}$ but $a_i$ may be not equal to $b_i$ for $i=\{n-k+1,\dots,n\}$.

Define the geometric median of $(a_1, \dots, a_N)$ and $(b_1, \dots, b_N)$ as \begin{equation} x^{(a)}_\star= \text{argmin}_{x \in \mathbb{R}^d} \sum_{i=1}^{N} \| x - a_i \|_2. \end{equation} \begin{equation} x^{(b)}_\star= \text{argmin}_{x \in \mathbb{R}^d} \sum_{i=1}^{N} \| x - b_i \|_2. \end{equation}

My question is there any upperbound on the following quantitiy? \begin{equation} \| x^{(a)}_\star - x^{(b)}_\star\|_2 \end{equation}