<p>This is the <a href="https://en.wikipedia.org/wiki/Geometric_median" rel="noreferrer">geometric median problem</a>. There is a nearly linear time algorithm based on interior point methods due to <a href="https://arxiv.org/abs/1606.05225" rel="noreferrer">Cohen et al.</a>: to find a $(1+\varepsilon)$-approximation their algorithm runs in time $O(nd\log^3(n/\varepsilon))$. Note that some approximation is necessary, because the optimal solution may not be rational and doesn't have to be a simple function of the input. See the paper for references to prior work. </p>

CC BY-SA 3.0
2017-10-10T05:32:07.750Z
2017-10-10T05:32:07.750Z
Sasho Nikolov
<p>Given points $x_1, x_2, \cdots, x_n \in \mathbb{R}^d$. What is the complexity of computing
$$
argmin_{x}\left(\sum_{i=1}^n ||x_i-x||_2\right) 
$$</p>

<reference-request><optimization><clustering>
Centroid in $\ell_2$ distance
Vivek Bagaria
# Centroid in $\ell_2$ distance

(Asked by: username_0 on 2017-10-10)

Given points $x\_1, x\_2, \cdots, x\_n \in \mathbb{R}^d$. What is the complexity of computing
$$
argmin\_{x}\left(\sum\_{i=1}^n ||x\_i-x||\_2\right)
$$

**Tags:** reference-request, optimization, clustering

---

## 1 answers

### Answer by username_1 on 2017-10-10. Score: 5

This is the [geometric median problem](https://en.wikipedia.org/wiki/Geometric_median). There is a nearly linear time algorithm based on interior point methods due to [Cohen et al.](https://arxiv.org/abs/1606.05225): to find a $(1+\varepsilon)$-approximation their algorithm runs in time $O(nd\log^3(n/\varepsilon))$. Note that some approximation is necessary, because the optimal solution may not be rational and doesn't have to be a simple function of the input. See the paper for references to prior work.


---

