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.

I'd love your help with this following problem:

Given $y_1,y_2,\ldots,y_N \in \mathbb{R}$, I need to prove that $f(x)= \sum \limits_{i=1}^{N}|x-y_i|^2$ gets a minimum, and to find it.

I don't know really how to solve it,

Any suggestions?

Thanks!

share|improve this question
    
I changed "a minima" to "a minimum". The former is plural; the latter is singular. "This minimum is...." or "These minima are...." Lots of students get confused about this. –  Michael Hardy Feb 14 '12 at 16:17

2 Answers 2

up vote 8 down vote accepted

You can use calculus, or not. Expand the squares. We get $$f(x)=Nx^2-2x\sum_{i=1}^N y_i+\sum_{i=1}^N y_i^2.$$ This is a quadratic in $x$, and the coefficient of $x^2$ is positive. So the curve $y=f(x)$ is an upward facing parabola.

Thus $f(x)$ has a minimum, where the parabola is lowest, and it can be found in the usual calculus way.

But I would like to do it another way. Multiply $f(x)$ by $N$. We get $$Nf(x)=N^2x^2-2xN\sum y_i + N\sum y_i^2.$$ Complete the square. We get $$Nf(x)=\left(Nx-\sum y_i\right)^2+N\sum y_i^2-\left(\sum y_i\right)^2.$$ Then $Nf(x)$ is obviously minimized when $Nx-\sum y_i=0$, that is, when $$x=\frac{\sum y_i}{N},$$ since $\left(Nx-\sum y_i\right)^2$ is always $\ge 0$. The minimum value of $Nf(x)$ is therefore $N\sum y_i^2-\left(\sum y_i\right)^2$. It follows that the minimum value of $f(x)$ is equal to $$\sum y_i^2-\frac{1}{N}\left(\sum y_i\right)^2.$$

Remark: This is not just an "exercise": it has great practical importance, in Statistics and elsewhere. I will change the notation to the one the problem should have used, and write $x_i$ instead of $y_i$. So we have $N$ data points (numbers) $x_1,x_2,\dots,x_N$, and would like to find the value of $x$ which is in some sense nearest to our collection of data points, which best fits them. For technical reasons, we want to minimize the sum of the squares of the deviations from $x$ to the $x_i$, the sum of the squares of the "errors." So we are minimizing $$\sum_{i=1}^N(x-x_i)^2.$$ The minimum value is reached, as we saw, when $x=\frac{\sum x_i}{N}$. This is the average (mean) of the $x_i$.
Actually, we usually want to minimize $\frac{f(x)}{N}$. By our calculation, the minimum value of this is $$\frac{\sum x_i^2}{N}-\left(\frac{\sum x_i}{N}\right)^2,$$ which is usually called the variance of the collection of data points $x_i$. The variance in a sense measures how far, on average, the $x_i$ depart from the mean.

share|improve this answer
    
Interesting.. Even though I wanted calculus solution, it was nice to read. Thanks a lot! –  Jozef Feb 14 '12 at 11:54
    
@Jozef: For calculus, the differentiation is trivial. Don't let the absolute values confuse you, the terms are just $(x-y_i)^2$, with derivatives $2(x-y_i)$. Add up, set equal to $0$. We get $x=(\sum y_i)/N$. Have min there because of the geometry. For min value, just substitute. I knew you wanted a calculus solution, and sort of gave one. After the first expansion, I wrote that the thing could be minimized in the usual calculus way. Just a fancied up version of minimize $3x^2-2x+7$. If we are going to use calculus, the expand step is unnecessary, we can differentiate immediately. –  André Nicolas Feb 14 '12 at 15:57
    
+1. Beautiful solution. –  Dejan Govc Feb 15 '12 at 2:44

Hint: For what $x$ does $f'(x)=0$?

share|improve this answer
    
I got confused, Do you consider $f$ a function form $\mathbb{R} \to \mathbb{R}$? –  Jozef Feb 14 '12 at 8:21
    
Yes: $f: \mathbb R \to \mathbb R,\quad x \longmapsto \sum (x-y_i)^2$ –  Alexander Thumm Feb 14 '12 at 8:23
    
O.k, $f'(x)= \sum_{i=1}^{N}2|x-y_i|$, so only if $y_i$ are all equal and $y_i=x$ , $f'(x)=0$, right? –  Jozef Feb 14 '12 at 8:33
    
No $f'(x) = 2\left( Nx - \sum y_i \right)$, so $f'(x) = 0$ if and only if $x = \frac{1}{N}\sum y_i$. –  Alexander Thumm Feb 14 '12 at 8:36
    
O.k, What should i do in order to see if it is minimum or not? –  Jozef Feb 14 '12 at 11:45

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.