My Math Forum  

Go Back   My Math Forum > College Math Forum > Linear Algebra

Linear Algebra Linear Algebra Math Forum


Thanks Tree2Thanks
  • 1 Post By zylo
  • 1 Post By zylo
Reply
 
LinkBack Thread Tools Display Modes
January 14th, 2018, 10:21 AM   #1
Senior Member
 
Joined: Jan 2017
From: Toronto

Posts: 175
Thanks: 2

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 ______?

My Answer: Ax = b

Am I correct?
zollen is offline  
 
January 23rd, 2018, 10:15 AM   #2
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 1,364
Thanks: 100

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:
Online LaTeX Equation Editor - create, integrate and download
The following, though a little slow and wordy, is very helpful:
https://www.khanacademy.org/math/linear-algebra
zylo is offline  
January 24th, 2018, 11:44 AM   #3
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 1,364
Thanks: 100

Quote:
Originally Posted by zylo View Post
.......
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
Thanks from zollen
zylo is offline  
February 3rd, 2018, 10:45 AM   #4
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 1,364
Thanks: 100

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.)
Thanks from zollen
zylo is offline  
Reply

  My Math Forum > College Math Forum > Linear Algebra

Tags
question, square



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Completing the Square question. GuyDoingMathFoiled Algebra 10 January 9th, 2014 03:24 PM
Question about square roots! Antuanne Algebra 2 May 8th, 2013 02:37 PM
question about square root sangching Linear Algebra 1 May 18th, 2011 03:26 PM
Square root question mmmboh Calculus 4 October 28th, 2008 06:51 PM
Square roots question Time Elementary Math 8 August 13th, 2007 08:47 AM





Copyright © 2018 My Math Forum. All rights reserved.