2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Andrew
    Feb 28 '16 at 6:19
  • $\begingroup$ 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. $\endgroup$
    – Jean Marie
    Feb 28 '16 at 6:51
  • $\begingroup$ 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$ $\endgroup$
    – reuns
    Feb 28 '16 at 7:47
0
$\begingroup$

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$...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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