Ytukyg

How do I proceed to find $nabla_A||Ax - y||^2$ where $A in mathbb{R}^{ntimes n}$ and $x,y in mathbb{R}^n$ and the norm is the Euclidean norm.

Attempt so far

$$||Ax - y||^2 = (Ax-y)^T(Ax-y) = x^TA^TAx - 2x^TAy + y^Ty $$

$$ nabla_A(x^TAy) = xy^T$$

Where I am stuck

I don't know how to tackle the $x^TA^TAx$ term since if I try to apply chain rule, I will have to differentiate a matrix with respect to a matrix.

Before we start deriving the gradient, some facts and notations for brevity:

• Trace and Frobenius product relation $$leftlangle A, B Crightrangle={rm tr}(A^TBC) := A : B C$$


• Cyclic properties of Trace/Frobenius product
  begin{align}
  A : B C
  &= BC : A \
  &= A C^T : B \
  &= {text{etc.}} cr
  end{align}
  

Let $f := left|Ax-y right|^2 = Ax-y:Ax-y$.

Now, we can obtain the differential first, and then the gradient.
begin{align}
df
&= dleft( Ax-y:Ax-y right) \
&= left(dA x : Ax-yright) + left(Ax-y : dA xright) \
&= 2 left(Ax - yright) : dA x \
&= 2left( Ax-yright)x^T : dA\
end{align}

Thus, the gradient is
begin{align}
frac{partial}{partial A} left( left|Ax-y right|^2 right)= 2left( Ax-yright)x^T.
end{align}

For matrices, the most easy way is often to get back to definition of differentiability, i.e. :

$$||(A+H)x - y||^2-||Ax - y||^2=L_A(H) + o(|H|)$$

With $L_A$ a linear map.

We begin with :
$$||(A+H)x - y||^2=langle Ax+Hx-y , Ax+Hx-y rangle.$$

Then we have :

$$||(A+H)x - y||^2= langle Ax-y,Ax-yrangle + 2langle Hx,Ax -yrangle + langle Hx,Hxrangle.$$

To conclude : $$||(A+H)x - y||^2-||Ax - y||^2=2langle Hx,Ax -yrangle + o (|H|)$$

Thus :

$$left(nabla_A||Ax - y||^2right)_{i,j}=2langle E_{i,j}x,Ax -yrangle$$

With $E_{i,j}$ the matrix with a $1$ at row $i$ and column $j$ and $0$ otherwise.