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?

  • 3
    $\begingroup$ 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. $\endgroup$ – stochasticboy321 Nov 26 '15 at 14:57
  • $\begingroup$ so, is there a closed solution for the minimum of the weighted geometric median for a finite number of points? $\endgroup$ – Lee Nov 26 '15 at 15:07
  • 2
    $\begingroup$ 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. $\endgroup$ – stochasticboy321 Nov 26 '15 at 15:13
  • $\begingroup$ That link to the wikipedia page on the Weber problem was exactly what I needed. Thank you from the year 2020, @stochasticboy321. $\endgroup$ – Thomas Winckelman Mar 30 '20 at 1:11

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$

  • $\begingroup$ How can I generalize your answer to multiple dimensions? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.