Can anyone please explain step-by-step why the x,A,b position as such? For example in step 2 'Expand the error', why isn't is (Ax)^2*x -2(Ax)(b)+b^2? In step 3 why setting derivative = 0, the 2x^T(A^Tb) in previous step & ||b||^2 disappear? Thx.
Asked
Active
Viewed 3,226 times
2
-
This question comes up a lot, but I think expanding is a mistake. The most elegant way to compute the gradient of $f(x) = | Ax - b |^2$ is to note that $f(x) = g(h(x))$, where $h(x) = Ax - b$ and $g(u) = | u |^2$. The derivatives of $g$ and $h$ are $g'(u) = 2u^T, h'(x) = A$. So by the chain rule $f'(x) = g'(h(x)) h'(x) = 2 (Ax - b)^T A$. Thus $\nabla f(x) = f'(x)^T = 2 A^T (Ax - b)$. Now setting $\nabla f(x) = 0$, we find that $A^T(Ax - b) = 0$ , or in other words $(A^T A) x = A^T b$. – littleO Mar 19 '20 at 03:57
-
Please use MathJax for typesetting math. – StubbornAtom Mar 19 '20 at 06:21
1 Answers
5
By definition, $$\lVert Ax-b\rVert_2^2 = \langle Ax-b, Ax-b\rangle$$ which you can expand by (bi)linearity of the inner product:
$$\begin{align}\lVert Ax-b\rVert_2^2 &= \langle Ax-b, Ax\rangle - \langle Ax-b, b\rangle\\ &=\langle Ax, Ax\rangle - \langle b, Ax\rangle - \langle Ax, b\rangle+\langle b, b\rangle\\ &=\langle Ax, Ax\rangle - 2\langle Ax, b\rangle+\langle b, b\rangle\\ &=(Ax)^TAx - 2(Ax)^Tb +\lVert b\rVert_2^2\\ &=x^TA^TAx - 2x^TA^Tb +\lVert b\rVert_2^2\end{align}$$ using that (i) $\langle Ax, b\rangle=\langle b, Ax\rangle$ and (ii) $(Ax)^T = x^T A^T$.
When you set the derivative to 0, terms do not "disappear". $- 2x^TA^Tb$ gives you a $- 2A^Tb$, and $x^TA^TAx$ gives you a $2A^TAx$. The constant term $\lVert b\rVert_2^2$, indeed, does disappear (it's a constant, so when you differentiate with regard to $x$...).
Clement C.
- 67,323