How to write the first term of Taylor expansion for a function matrix?

Question

Assume $F(A)=\left\| A^N v-w \right\|^2$ where $A$ is a square matrix and $v$ and $w$ are two constant vectors and $N$ is a positive integer. Also, the norm is the Euclidean norm. How to write the first order approximation of function $F(A)$? In other words, how to write it as $F(A+tB)=F(A)+t*D*B + H.O.T$? What is $D$?

Answer 1

$F(A+tB)=F(A)+tDF_A(B)+o(t)$ where

$DF_A(B)=2(A^N v-w)^T(BA^{N-1}+ABA^{N-2}+\cdots +A^{N-1}B)v$.

If $A\in M_n$, then the calculation of $DF_A(B)$ has complexity

$O(n^2N^2)$ if you don't know the $(A^k)_{k\leq N}$ and

$O(n^2N)$ otherwise.

You can also use the tensor product of matrices.

EDIT. Yes, we can write the gradient. Let $K=2v(A^Nv-w)^T\in M_n$.

$DF_A(B)=tr(K(BA^{n-1}+ABA^{n-2}+\cdots+A^{n-1}B))=$

$tr((A^{n-1}K+A^{n-2}KA+\cdots+KA^{n-1})B)=$

$< (A^{n-1}K+A^{n-2}KA+\cdots+KA^{n-1})^T,B>$ for the scalar product $<U,V>=tr(U^TV)$.

Then the gradient is

$\nabla(F)(A)=(A^{n-1}K+A^{n-2}KA+\cdots+KA^{n-1})^T$.