Linear Algebra Linear Algebra Math Forum

 January 14th, 2018, 11:21 AM #1 Senior Member   Joined: Jan 2017 From: Toronto Posts: 209 Thanks: 3 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? January 23rd, 2018, 11:15 AM #2 Banned Camp   Joined: Mar 2015 From: New Jersey Posts: 1,720 Thanks: 126 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 January 24th, 2018, 12:44 PM   #3
Banned Camp

Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 126

Quote:
 Originally Posted by zylo ....... 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 February 3rd, 2018, 11:45 AM #4 Banned Camp   Joined: Mar 2015 From: New Jersey Posts: 1,720 Thanks: 126 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 Tags question, square Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post GuyDoingMathFoiled Algebra 10 January 9th, 2014 04:24 PM Antuanne Algebra 2 May 8th, 2013 03:37 PM sangching Linear Algebra 1 May 18th, 2011 04:26 PM mmmboh Calculus 4 October 28th, 2008 07:51 PM Time Elementary Math 8 August 13th, 2007 09:47 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      