# Proof of least squares approximation lemma

I'm trying to give a proof to the following lemma:

Suppose $b \in R^n$ and $A$ is a $n$ by $m$ matrix, where $m < n$, and that $A^TA$ is an invertible matrix. Then the unique minimiser of the function $v \rightarrow |Av-b|^2$ is given by $v_0 = (A^TA)^{-1}A^Tb$.

I've been instructed to write $Av = b + e$ where $e$ is the error and to try and minimise $|e|^2$. To do this, I've further been told to find the derivatives of

$|Av-b|^2 = \sum_{i=1}^{n}|(Av)_i-b_i|^2 = \sum_{i=1}^{n}|\sum_{j=1}^{m}A_{ij}v_j-b_i|^2$

in the variables $v_j$ for $j = 1,...,m$. There's more for me to do, of course, but I just can't get started on the problem because I have no clue how to even find the derivatives. I'm a first year maths student, so I've never encountered anything like this before. I've spent the last hour and a half trying in vain to do in ways that seem to make sense, but do little more than change $v_j$ to $v'_j$. If it helps in giving any pointers, I'm supposed to set the derivatives to $0$ at a minimiser $v_0$ once I've found them.

Thanks

• the proof uses the method of /Lagrange multipliers/ applied to the sum of squares of deviations: partial derivatives are necessary to find the stationary point Feb 28 '16 at 6:19
• Of course, this global approach is more straighforward (and lesse tedious...), but, as I understand, @J Weatherspoon has been guided to take a component by component approach by his instructor. Feb 28 '16 at 6:51
• write $b = A c + d$ where $\langle A^Tc,d\rangle = 0$, so $(A^T A)^{-1} A^T b = c$, which is the minimizer of $f(v) = ||Av-b||^2$ since $f(v) \ge d$ Feb 28 '16 at 7:47

First of all, replace the absolute values by parenthesis in the RHS:

$$E^2=\|Av-b\|^2 = \sum_{i=1}^{n}(\sum_{j=1}^{m}A_{ij}v_j-b_i)^2$$

then take the (partial) derivative with respect, for example, to $v_1$; you will get this equation that we equate to zero (necessary condition for a minima)

$$\partial E^2/\partial v_1 = 2\sum_{i=1}^{n}A_{i1}(\sum_{j=1}^{m}A_{ij}v_1-b_i)=0$$

Thus

$$\sum_{i=1}^{n}\sum_{j=1}^{m}A_{i1}A_{ij}v_1=\sum_{i=1}^{n}A_{i1}b_i$$

Do the same with all $v_k$s. You will end up with an expression where you will recognize $A^TAV=A^Tb$...