Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we have $n$ real numbers $a_1, a_2, \ldots, a_n$. We know that the solution which minimizes $$ \sum_{i=1}^n |x-a_i| $$ is $x^*=$ median of $a_1, a_2\ldots, a_n$.

Now suppose that we should choose $k<n$ numbers, namely $x^*_1, x^*_2, \ldots, x^*_k$ which corresponds to the $a_i$'s. For example $x^*_1$ corresponds to $a_1$ and $a_2$; $x^*_2$ corresponds to $a_3$, $a_4$ and $a_5$ etc. which minimizes $$ |x^*_1-a_1| + |x^*_1-a_2| + |x^*_2-a_3|+ x^*_2-a_4|+ |x^*_2-a_5|+ \ldots + |x^*_k-a_n| $$

Let me give a more concrete example:

Suppose we have 2,4,5,11,14 and $k=2$. Thus we need to choose $x_1$ and $x_2$. If we choose $x_1=5$ and associate it to 2,4 and 5; $x_2=11$ and associate it to 11 and 14 we get $$ |2-5|+|4-5|+|5-5|+|11-11|+|14-11|=3+1+3=7 $$

The question is how we can choose such $x_k$'s and how we should associate them to $a_i$'s. Is there any algorithm?

share|improve this question
2  
Sounds like you are asking for algorithms for K-means clustering. Does the standard algorithm section in above wiki page help? –  achille hui Feb 8 '13 at 0:51
    
@achillehui: Thanks, that is what I have been looking for. –  neticin Feb 8 '13 at 2:25

1 Answer 1

If you break your sum into multiple sums, one for each $x_k$, you see that each $x_k$ affects only one sum, and each sum depends on only $x_k$. Therefore, to minimize the overall total, you minimize each individual sum. Therefore, $x_k$ should be the median of the $a_i$ corresponding to it.

share|improve this answer
    
How can I choose the $a_i$ corresponding to $x_k$? –  neticin Feb 7 '13 at 23:45
    
You said in the problem that you had $X_k$ corresponding to certain $a_i$'s. If it isn't just given as part of the problem, then I do not understand the problem set up. –  Aaron Feb 8 '13 at 5:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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