distance between coordinate-wise median and geometric median

178 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$. For $i \in \{1,\dots,N\}$, let $a^{(i)}$ be a vector in $B_d(1)$.

Define the geometric median of $a^{(1)}, \dots, a^{(N)}$ as \begin{equation} x_\star^{(2)} = \text{argmin}_{x \in \mathbb{R}^d} \sum_{i=1}^{N} \| x - a^{(i)} \|_2. \end{equation}

Also, define the coordinate-wise median of $a^{(1)}, \dots, a^{(N)}$ as

\begin{equation} x_\star^{(1)} = \text{argmin}_{x \in \mathbb{R}^d} \sum_{i=1}^{N} \| x - a^{(i)} \|_1. \end{equation}

My question is how we can characterize the following? \begin{equation} \sup_{a^{(1)}\in B_d(1), \dots, a^{(N)} \in B_d(1)} \| x_\star^{(1)} - x_\star^{(2)} \|_2. \end{equation}