# minimizing the sum of weighted absolute distance

Let $x_1, \ldots, x_n \in \mathbb{R}^d$ denote $n$ points in $d$-dimensional Euclidean space, and $w_1, \ldots, w_n \in \mathbb{R}_{\geq 0}$ any non-negative weights.

$\arg\min_{\mu \in \mathbb{R}^d} \sum_{i=1}^n w_i | x_i-\mu| = median\{x_1, \ldots, x_n \}?$

I understand why the median of $\{x_1, \ldots, x_n \}$ minimizes the function without the weights. But I am not sure if the median is what minimizes the function with the weights, should I use Lagrange multiplier to solve this?

• The result claimed is incorrect when the $w_i$s are not equal. Consider the case $w_j < \epsilon$ for $j>1$ and $w_1$ very large. The minimiser then is very close to $x_1$, which need not be the geometric median of the $\{x_i\}$. I believe this equation is generally used to define the weighted geometric median. This wiki article on the Weber Problem may be germane. – stochasticboy321 Nov 26 '15 at 14:57
• so, is there a closed solution for the minimum of the weighted geometric median for a finite number of points? – Lee Nov 26 '15 at 15:07
• I don't get the term 'minimum of the median'. However, if you simply mean the median itself, I don't think so. IIRC there isn't one for the unconstrained median either. BTW, recall that the case where $w_i =1$ is also the definition of the median in the usual sense. – stochasticboy321 Nov 26 '15 at 15:13

What minimizes your weighted is again the median !!! But not the median of $x_1,x_2,...$.

A value that minimizes your sum will be a number $\mu$ such that

$$\sum_{i\in \{1,2,...,n\}, x_i>\mu} w_i < \frac {\sum_{i=1}^n w_i}{2}$$

$$\sum_{ i\in \{1,2,...,n\},\,\, x_i<\mu} w_i < \frac {\sum_{i=1}^n w_i}{2}$$

Note that this $\mu$ will also a median. It is a median of the random variable defined on the sample space ${1,2,...,n}$ that sends $i$ to $x_i$. In this probability space, the probability of occurrence of $i$ is $\frac {w_i} {w_1+...+w_n}$

Opps! ! I just noted that your $x_i$ can be vectors, therefore my answer only works when $d=1$

• How can I generalize your answer to multiple dimensions? – Lee Nov 27 '15 at 10:07

The problem you have stated is the weighted L1 median (sometimes called the weighted geometric median) of your data. There are many references on the topic: https://www.google.com/search?q=l1+median

A concise reference along with an algorithm is: http://www.stat.rutgers.edu/home/cunhui/papers/39.pdf

However, note that the Vardi-Zhang process needs to be adjusted for data having repeated values. If you scan the literature, there are some references that describe this adjustment.