My Math Forum (http://mymathforum.com/math-forums.php)
-   Linear Algebra (http://mymathforum.com/linear-algebra/)
-   -   Another Least Square question.. (http://mymathforum.com/linear-algebra/343217-another-least-square-question.html)

 zollen January 14th, 2018 11:21 AM

Another Least Square question..

The partial derivatives of $\displaystyle ||Ax||^2$ with respect to $\displaystyle x_1......x_n$ fill the vector $\displaystyle 2A^TAx$.
The derivatives of $\displaystyle 2b^TAx$ fill the vector $\displaystyle 2A^Tb$.

So the derivatives of $\displaystyle ||Ax - b||^2$ are zero when ______?

Am I correct?

 zylo January 23rd, 2018 11:15 AM

The following utilizes the Einstein summation convention: sum over repeated integers, for example $\displaystyle b^{2}=b_{i}b_{i}$

$\displaystyle ||Ax-b||^{2} = [Ax-b]_{i} [Ax-b]_{i}= [[Ax]_{i}-b_{i}][[Ax]_{i}-b_{i}]$

$\displaystyle =[Ax]_{i}[Ax]_{i} -2b_{i}[Ax]_{i}+b^{2}$

$\displaystyle [Ax]_{i}[Ax]_{i} = A_{ij}x_{j} A_{ik}x_{k} = ||Ax||^{2}$

$\displaystyle \frac{\partial ||Ax||^{2}}{\partial x_{m}}= A_{ij}\delta_{jm} A_{ik}x_{k} + A_{ij}x_{j} A_{ik}\delta_{jm} = 2A_{im}A_{ik}x_{k}=2[A^{T}Ax]_{m}$

$\displaystyle 2b_{i}[Ax]_{i}= 2b_{i}A_{ij}x_{j}$

$\displaystyle \frac{\partial 2b_{i}[Ax]_{i}}{\partial x_{m}} = 2b_{i}A_{ij}\delta _{jm}= 2b_{i}A_{im} = 2A^{T}_{mi}b_{i}$

$\displaystyle \frac{\partial ||Ax-b||^{2}}{\partial x_{m}}=2[A^{T}Ax-A^{T}b]_{m}=0$, all m, $\displaystyle \rightarrow$

$\displaystyle A^{T}Ax-A^{T}b=0$

which is the equation for least squares approximation of Ax=b = 0 when it doesn't have a solution, ie, when you minimize the distance between Ax and b.
The utility of the Einstein summation convention never ceases to amaze me.
I first tried the following but got stuck:

$\displaystyle ||Ax-b||^{2}=[Ax-b]^{T}[Ax-b]= [x^{T}A^{T}-b^{T}][Ax-b]$

$\displaystyle \frac{\partial( x^{T}A^{T}Ax)}{\partial x_{i}}$ = ?????

For math equations I use:
The following, though a little slow and wordy, is very helpful:

 zylo January 24th, 2018 12:44 PM

Quote:
 Originally Posted by zylo (Post 587504) ....... I first tried the following but got stuck: $\displaystyle ||Ax-b||^{2}=[Ax-b]^{T}[Ax-b]= [x^{T}A^{T}-b^{T}][Ax-b]$ $\displaystyle \frac{\partial( x^{T}A^{T}Ax)}{\partial x_{i}}$ = ????? ..........
Actually, it can be done:

$\displaystyle ||Ax||^{2} = x^{T}[A^{T}A]x = \begin{vmatrix} x_{1} &x_{2} & . & . & x_{n}\end{vmatrix}[A^{T}A]\begin{vmatrix}x_{1}\\ x_{2}\\ .\\ .\\ x_{n}\end{vmatrix}\\$

$\displaystyle \frac{\partial (||Ax||^{2})}{\partial x_{m}}=\begin{vmatrix} 0 &. & 1 & . & 0\end{vmatrix}[A^{T}A]\begin{vmatrix}x_{1}\\ x_{2}\\ .\\ .\\ x_{n}\end{vmatrix} +\begin{vmatrix} x_{1} &x_{2} & . & . & x_{n}\end{vmatrix}[A^{T}A]\begin{vmatrix}0\\ .\\ 1\\ .\\ 0\end{vmatrix}\\$, 1 in the m position

$\displaystyle =[A^{T}A]_{row m}x + x^{T}[A^{T}A]_{col m}=2[[A^{T}A]x]_{m}\\$

Following through with other term gives, as before.

$\displaystyle \frac{\partial ||Ax-b||^{2}}{\partial x_{m}}=2[A^{T}Ax-A^{T}b]_{m}=0$, all m, $\displaystyle \rightarrow$

$\displaystyle A^{T}Ax-A^{T}b=0$

Another good reference on the subject is the great tutorial
https://ocw.mit.edu/courses/mathemat...ideo-lectures/
See Lectures 15 and 16

 zylo February 3rd, 2018 11:45 AM

Using a different notation:

If $\displaystyle x^{T}=[x_{1}\ x_{2}......x_{n}],\ \ \frac{\partial x^{T}}{\partial x_{i}}= [0\ \ 0..1..0]=e_{i}^{T}$
For a vector $\displaystyle x,\ \ x^{2}=x^{T}x=xx^{T}$

$\displaystyle ||Ax-b||^{2}=[Ax-b]^{T}[Ax-b]= [x^{T}A^{T}-b^{T}][Ax-b]$
$\displaystyle =x^{T}A^{T}Ax-x^{T}A^{T}b-b^{T}Ax -b^{2}=x^{T}A^{T}Ax-2x^{T}A^{T}b-b^{2}$
$\displaystyle \frac{\partial() }{\partial x_{_{i}}}=e_{i}^{T}A^{T}Ax+x^{T}A^{T}Ae_{i}-2e_{i}^{T}A^{T}b=2e_{i}^{T}[A^{T}Ax-A^{T}b]=0,$ all i

$\displaystyle A^{T}Ax-A^{T}b=0$

(In regression, you are dealing with a situation where A doesn't have an inverse.)

 All times are GMT -8. The time now is 10:20 AM.