Second derivative of norm of matrix power $\lVert y - A^kx \rVert$

Question

I am looking for the second derivative w.r.t $A$ (and $x$ and $y$, but those are a little easier):

$$ \frac{\partial^2}{\partial A^2} \frac{1}{2} \lVert y - A^kx \rVert_2^2 $$

I can find the first derivative with www.matrixcalculus.org:

$$ \frac{\partial}{\partial A} \frac{1}{2} \lVert y - A^kx \rVert_2^2 = -k \cdot diag(y - A^kx)A^{k-1}\cdot diag(x) $$

But handling the "diag" operator wasn't clear. I am attempting/hoping to show that the Lipschitz constant used for gradient descent depends on $k$.

Answer 1

The tricky part is the differential $$\eqalign{ dA^k &= \sum_{j=0}^{k-1} A^{j}\,dA\,A^{k-j-1}\cr }$$ Define $w = (A^kx-y)$ and $B=A^T\,\,$ then find the gradient (first derivative) $$\eqalign{ \phi &= \tfrac{1}{2}\|w\|^2_2 = w:w \cr d\phi &= 2w:dw = 2w:dA^kx = 2wx^T:dA^k \cr &= \sum_{j=0}^{k-1} 2wx^T:A^{j}\,dA\,A^{k-j-1} \cr &= \sum_{j=0}^{k-1} 2B^{j}wx^TB^{k-j-1}:dA \cr G=\frac{\partial\phi}{\partial A} &= \sum_{j=0}^{k-1} 2B^{j}wx^TB^{k-j-1} \cr }$$ where a colon denotes the trace/Frobenius product, i.e. $M:P={\rm Tr}(M^TP)$

Note that the gradient is a matrix. That means that the Hessian (second derivative) will be a fourth-order tensor -- which is the reason why the website won't try to calculate it.

In order to calculate the Hessian, the $w$ and $B^i=(A^T)^i$ terms must be differentiated leading to a complicated double summation. Start by finding the differential of the gradient. $$\eqalign{ dG &= 2\sum_{j=0}^{k-1} &dB^{j}wx^TB^{k-j-1}+B^{j}dA^kxx^TB^{k-j-1}+B^{j}wx^TdB^{k-j-1} \cr &= 2\sum_{j=0}^{k-1}\Bigg(&\sum_{i=0}^{j-1}B^{i}\,dB\,B^{j-i-1}wx^TB^{k-j-1} + \sum_{i=0}^{k-1}B^{j}A^{i}\,dA\,A^{k-i-1}xx^TB^{k-j-1} \cr &\,&+ \sum_{i=0}^{k-j-2}B^{j}wx^TB^{i}\,dB\,B^{j-i-1} \Bigg) \cr }$$ At this point you can use vectorization to flatten the matrices into vectors and calculate the Hessian as the matrix, i.e. $$g={\rm vec}(G),\,\,\,a={\rm vec}(A) \implies H=\frac{\partial g}{\partial a}$$ Or you can find the Hessian in tensor form using index notation.

Or perhaps the differential expression is sufficient for whatever purpose you have in mind.