Distance of a hyperplane from Geometric Median

24 Views Asked by At

Let $d,n \in \mathbb{N}$. Assume we have $n$ points, $x_1,\dots,x_n$ where for every $i \in \{1,\dots,n\}$, we have $x_i \in \mathbb{R}^d$. Define the geometric median as

$$ \theta^\star \in \arg\min_{\theta \in \mathbb{R}^d} \sum_{i=1}^n \lVert \theta - x_i \rVert $$

Fix a hyperplane $(w_0,\theta_0)$, i.e., $\{x \in \mathbb{R}^d: \langle x-\theta_0,w_0 \rangle=0\}$. For every $i \in \{1,\dots,n\}$, define the distance of $x_i$ to the hyperplane as $d_H(i)=\frac{|\langle x_i - \theta_0, w_0 \rangle|}{\lVert w_0 \rVert}$.

Question

Given $\alpha > 0$, is there an approach solely based on the distances of the data points to the hyperplane, i.e., $d_H(i)$, that allows us to determine whether the distance from the hyperplane $(w_0,\theta_0)$ to the geometric median is greater or smaller than $\alpha$?

Context

If instead of the hyperplane, we have a fixed point, the answer is positive. See Lemma 2.1 in this paper. In particular, if a fixed point is far from a large fraction of the datapoints, then it is also far from the geometric median.