Hessian matrix of $ \| Ax -b \|_2$

Question

I need to compute the Hessian matrix of $ \| Ax -b \|_2$ with respect to x where $A$ is $ m \times n $ matrix, $x$ is $ n \times 1 $ vector and $b$ is $ m \times 1 $ constant vector. It is not so hard to compute the gradient of $ \| Ax -b \|_2$ or the Hessian matrix for $ (\| Ax -b \|_2)^2$ but not sure how to make progress on the Hessian matrix of $ \| Ax -b \|_2$

Answer 1

$$ \nabla \|x\| = x (x^Tx)^{-1/2} = \frac{x}{ \|x\| } \implies$$ $$ (\nabla^2 \|x\|)_{ij} = \frac{ \partial \frac{x_i}{ \|x\| } } {\partial x_j} = \frac{ \frac{ \partial x_i} { \partial x_j} \|x\| - \|x\|^{-1}x_i x_j } { \|x\|^2 } \implies \\\\ \nabla^2 \|x\| = \frac{ I }{\|x\|}- \frac{ x x^T } {\|x\|^3 } \implies \\\\ \nabla^2 \|x-b\| = \frac{ I }{\|x-b\|} - \frac{ (x-b) (x-b)^T } {\|x-b\|^3 } $$

We now define $ g(x) = \|x-b\| $ and $ h(x) = g(Ax) = \|Ax-b\| $ and use the identity $ \nabla^2 h(x) = A^T \nabla^2 g(Ax) A $ and have

$ \nabla^2 \|Ax-b\| = A^T \nabla^2 (\|x-b\|)(Ax) A =\\\\ A^T \left( \frac{ I }{\|Ax-b\|}- \frac{ (Ax-b) (Ax-b)^T } {\|Ax-b\|^3 } \right) A $

Answer 2

First write down your function $$f(x_1,...,x_n)=\sqrt{(\sum_{j=1}^na_{1j}x_j-b_1)^2+...+(\sum_{j=1}^na_{mj}x_j-b_m)^2}$$ You can then calculate$ \nabla f(x_1,...,x_n) $ by the chain rule and thence $\text {Hess}_f(x_1,...,x_n)$ by the quotient and chain rules.