3
$\begingroup$

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!

  • 0
    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.2012-02-14

2 Answers 2

8

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.

  • 0
    @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.2012-02-14
3

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

  • 0
    f''(x) = 2N > 0 so it is a minimum.2012-02-14