# Using Linear Algebra, prove mean/average of set minimizes error (least squares?)

Say I have sets of $$n$$ points $$(x_i,y_i) \in \mathbb{R}^{2}$$. In a typical regression analysis, we find the equation of a "best-fit" line $$y=mx+b$$. By construction the system has no exact solution and so there is no 1 line going through all $$n$$ points.

Solving such a least-squares problem typically goes like this:

Let: $$A\,x = b$$, with

$$A\in\mathbb{R}^{n \times 2}$$ (known)
$$x\in\mathbb{R}^{2 \times 1}$$ (unknown)
$$b\in\mathbb{R}^{n \times 1}$$ (known)

The least squares solutions for $$x$$ minimizes $$\|A\,x-b\|$$ by ensuring $$(A^\top A)\hat{x}=A^\top b$$. This has the solution $$\hat{x}=\left(A^\top A\right)^{-1} A^\top b$$.

Writing $$A\hat{x}=b$$ in matrix form, $$\pmatrix{x_1&1\cr x_2&1\cr \vdots &\vdots \cr x_n&1\cr}\pmatrix{m\cr b\cr} =\pmatrix{y_1\cr y_2\cr \vdots\cr y_n\cr}$$

To find the line which provides the least error (least squares) results, we solve for $$\pmatrix{m\cr b\cr}=\left(A^\top A\right)^{-1} A^\top \pmatrix{y_1\cr y_2\cr \vdots\cr y_n\cr}$$ It can be shown that since $$A$$ has linearly independent columns, then this will always have a unique solution for vector $$\hat{x}=\pmatrix{m\cr b\cr}$$.

My question then is how can I use this technique to solve a much easier question:

"Prove that the mean (average) of the $$n$$ points $$(y_i) \in \mathbb{R}^{1}$$ (i.e. $$\bar{y}=\dfrac{\Sigma_1^n{y_i}}{n}$$) provides the least error solution under this framework."

I tried writing $$A\hat{x}=b$$ as

$$\pmatrix{1\cr 1\cr \vdots\cr 1}\pmatrix{\hat{x}} =\pmatrix{y_1\cr y_2\cr \vdots\cr y_n\cr}$$

Then trying to solve for the scalar $$\hat{x}$$ and then show that $$\hat{x}\!=\bar{y}$$. But I'm not confident my representation of $$A$$ is accurate.

When I solved for $$\hat{x}=\left(A^\top A\right)^{-1} A^\top \pmatrix{y_1\cr y_2\cr \vdots\cr y_n\cr}$$

I got $$\hat{x}=n\Sigma_1^n{y_i}$$, which clearly isn't $$\bar{y}$$. Any ideas on how to do this? Everyone else solved this using derivatives and I just want to show it using linear algebra instead...

Your derivation is correct but you made a slight mistake. You have $$A^\top A =[n],$$ and therefore the inverse is just $$[1/n],$$ then

$$\hat{x}=\left(A^\top A\right)^{-1} A^\top \pmatrix{y_1\cr y_2\cr \vdots\cr y_n\cr} = [1/n][\Sigma_1^n{y_i}] = [1/n \Sigma_1^n{y_i}],$$

which is what you want (you just get the result in "matrix" format)

Using explicit sums,

$$\begin{array}\\ D(a) &=\sum_{k=1}^n (y_k-a)^2\\ &=\sum_{k=1}^n (y_k^2-2ay_k+a^2)\\ &=\sum_{k=1}^ny_k^2-2a\sum_{k=1}^ny_k+\sum_{k=1}^na^2\\ &=\sum_{k=1}^ny_k^2-2a(n\hat{y})+na^2\\ D(\hat{y}) &=\sum_{k=1}^ny_k^2-2\hat{y}(n\hat{y})+n\hat{y}^2\\ &=\sum_{k=1}^ny_k^2-n\hat{y}^2\\ \end{array}$$

Therefore

$$\begin{array}\\ D(\hat{y})-D(a) &=(\sum_{k=1}^ny_k^2-n\hat{y}^2)-(\sum_{k=1}^ny_k^2-2a(n\hat{y})+na^2)\\ &=-n\hat{y}^2+2an\hat{y}-na^2\\ &=-n(\hat{y}^2-2a\hat{y}+a^2)\\ &=-n(\hat{y}-a)^2\\ &\le 0\\ &=0 \quad\text{only when } a = \hat{y}\\ \end{array}$$