There are multiple ways to extend the median to higher dimensions.
One natural way is to compute the coordinate-wise median, but this is not rotation-invariant. The coordinate-wise median is equivalent to computing $\underset{v \in \mathbb{R}^d}{\mathrm{argmin}} \sum_i^d \|x_i - v\|_1$. I.e., we are using the ell-1 geometry.
The geometric median is given by $\underset{v \in \mathbb{R}^d}{\mathrm{argmin}} \sum_i^d \|x_i - v\|_2$. Since this is definied in the ell-2 geometry, it is rotation invariant.
My question is about relating these two approaches. Specifically, let's force the coordinate-wise median to be rotation invariant by first randomly rotating the data before taking the coordinate-wise median and then undoing the rotation. This gives a randomized function. We can look at the expected value; that gives a deterministic function. Is this the geometric median? Beyond the expectation, we also would like some kind of bound on the variance.
Here's a more precise statement of the question.
Define two functions $f : (\mathbb{R}^d)^n \to \mathbb{R}^d$ and $g : (\mathbb{R}^d)^n \to \mathbb{R}$ as follows.
Let $x_1, \cdots, x_n \in \mathbb{R}^d$ and $x=(x_1, \cdots, x_n)$. Let $U \in \mathbb{R}^{d \times d}$ be a uniformly random unitary matrix -- i.e. $\mathbb{P}[U^TU=I]=1$ and the distribution of $Uv$ is the same for all unit vectors $v \in \mathbb{R}^d$. Define $y_U := \underset{v \in \mathbb{R}^d}{\mathrm{argmin}} \sum_i^n \|U(x_i-v)\|_1$ to be the coordinate-wise median of the points in the rotated geometry. (For simplicity, we can assume $n$ is odd so that the argmin is unique. If $n$ is even, we take the mean of the two points in the middle, as usual.) Now define $f(x) := \mathbb{E}_U[y_U]$ and $g(x) = \mathbb{E}_U[\|y_U-f(x)\|_2^2]$.
Question 1: Is $f(x) \in \underset{v \in \mathbb{R}^d}{\mathrm{argmin}} \sum_i^n \|x_i-v\|_2$? If not, is there some simpler expression for $f(x)$?
Question 2: Is there a "nice" upper bound on $g(x)$? E.g., an upper bound in terms of $\sum_{i,j}^n \|x_i-x_j\|_2^2$
The expectation of the rotated objective function is the desired objective function. I.e. $$\forall x~\forall v ~~~ \mathbb{E}\left[\sum_i^n \|U(x_i-v)\|_1\right] \propto \sum_i^n \|x_i-v\|_2.$$ Unfortunately, we need the argmin inside the expectation, so this equation does not answer the question, but it indicates why it is reasonable to conjecture a positive answer to question 1.