0

Let \begin{align}f(t) &= \|A(x+ty)-b\|^2_2 = (A(x+ty)-b)^T(A(x+ty)-b))\\ &= x^TA^TAx + 2tx^TA^TAy+t^2y^TA^TAy-2b^TA(x+ty)\end{align}

Then, letting $f'(t) = 0$, we have $$ t = \frac{(b^TAy)-x^TA^TAy}{y^TA^TAy}$$

Ok I am confused by the whole thing. The answer I am getting is completely different. I also used the fact $Ax = b$ and $x^TA^T = b^T$ and cancelled each other. Can someone please help me to come up with this answer? Thanks.

user136422
  • 247
  • 2
  • 4
  • 14

2 Answers2

1

The first order condition for minimum ($t$ is a scalar):

\begin{align} \frac{\partial f(t)}{\partial t} &=\frac{\partial}{\partial t}(A(x+ty)-b)^{\top}(A(x+ty)-b) \\ &=2\left[\frac{\partial}{\partial t}(tAy+Ax-b)\right]^{\top}(A(x+ty)-b) \\ &=2(Ay)^{\top}(A(x+ty)-b) \\ &=2y^{\top}A^{\top}(Ax-b)+2ty^{\top}A^{\top}Ay=0. \end{align} Thus,

$$ t^*=-\frac{y^{\top}A^{\top}(Ax-b)}{y^{\top}A^{\top}Ay}=\frac{y^{\top}A^{\top}(b-Ax)}{y^{\top}A^{\top}Ay}. $$

  • So, you only taken the partial derivative of the transpose part? – user136422 Apr 21 '14 at 14:27
  • Yes. This is the rule for quadratic forms: http://www.atmos.washington.edu/~dennis/MatrixCalculus.pdf (where $A=I$) –  Apr 21 '14 at 19:45
  • Sorry I am lost again here. How did you get $$=2[\frac{\partial}{\partial t}(tAy+Ax-b)]'(A(x+ty)-b)?$$ where did the 2 come from? – user136422 May 03 '14 at 02:48
  • 2 is because of square term (like derivative of $x^2$) –  May 03 '14 at 04:46
0

First write $(A(x+ty)-b)^T = (x+ty)^T A^T - b^T = t y^T A^T + (A x - b)^T$. Then we have \begin{align} f(t) &= (t y^T A^T + (A x - b)^T)(t A Y + (A x - b))\\ &= (y^TA^TAy) t^2 + 2(A x - b)^T A y t + (A x - b)^T (A x - b)\\ &= a t^2 + 2 \beta t + c \end{align} where $a = y^TA^TAy$, $\beta = (A x - b)^T A y$, $c = (A x - b)^T (A x - b)$. Note that $a$, $\beta$, and $c$ are constant scalars, while $t$ is the (only) scalar variable. This is a quadratic function, and calculus gives us, by simply taking the derivative of $f(t)$ with respect to the variable $t$ and letting $f'(t)=0$: \begin{equation} t = -\frac{\beta}{a} = \frac{(b - A x)^T A y}{y^TA^TAy} \end{equation}

Truong
  • 663