1

The problem is to find gradient and hessian of: $f(x) = \frac 1 2 || xx^T -A||_F^2$ given $A \in \mathbb{R^{n \times n}}$, $A$ is symmetric, $x \in \mathbb{R}^n$.
Notation: $||\cdot||_F$ is a Frobenius norm of a matrix.

My progress with problem halted after the application of chain rule: no matter the transformation I make, the inner function contains $\frac {\partial} {\partial x} xx^T$.

That is three dimensional object and to the best of my knowledge a matrix differentiation with respect to a vector is generally avoided.

I believe task requires to work around it, but I don't see a way.

Dmitri K
  • 1,401

3 Answers3

2

Define a new matrix variable $$\eqalign{ Y &= xx^T-A \cr dY &= dx\,x^T + x\,dx^T \cr }$$ Then write the function in terms of this new variable, and find its differential and gradient $$\eqalign{ f &= \frac{1}{2}Y:Y \cr df &=Y:dY = Y:(dx\,x^T + x\,dx^T) \cr &= (Y+Y^T):dx\,x^T \cr &= 2Yx:dx \cr g = \frac{\partial f}{\partial x} &= 2Yx \cr }$$ Now find the differential and gradient of the gradient (i.e the Hessian) $$\eqalign{ dg &= 2\,dY\,x + 2Y\,dx \cr &= 2\,(dx\,x^T + x\,dx^T)\,x + 2Y\,dx \cr &= 2\Big((x^Tx)I + xx^T +Y\Big)\,dx \cr H = \frac{\partial g}{\partial x} &= 2\Big((x^Tx)I + xx^T +Y\Big) \cr\cr }$$ In some of these steps, a colon is used to denote the trace/Frobenius product $$A:B = {\rm tr}(A^TB)$$

lynn
  • 3,396
1

I don't know why,but in textbook Matrix Algebra Theory computations and applications in statistics, The derivatives of $xx^T$ with respect to $x$ is $2x^T$ on page154,hope this helps.

shuo wang
  • 21
0

It was true, the workaround was to use a trace property $x^Tx = Tr(xx^T)$

$df(x) = \frac 1 2 d\ Tr[(xx^T -A)^T(xx^T -A)]= \frac 1 2 d\ Tr[ \cdot xx^T -xx^TA -Axx^T + A^2] = \frac 1 2 d[(x^Tx)^2 -2 x^Tx\ Tr(A)] = x^Tx \cdot x^Tdx - 2Tr(A)x^Tdx$
$\nabla f(x) = x^Txx - 2Tr(A)x$

$d^2(x) = d[x^Tx \cdot x^Tdx_1 - 2Tr(A)x^Tdx_1] = 2x^Tdx_2 \cdot x^Tdx_1 + x^Tx \cdot dx_2^Tdx_1 - 2Tr(A)dx_2^Tdx_1 =$
$2dx_2^Tx \cdot x^Tdx_1 + x^Tx \cdot dx_2^Tdx_1 - 2Tr(A)dx_2^Tdx_1$
$\nabla^2f(x) = xx^T + (x^Tx - 2Tr(A)) \cdot I$

Dmitri K
  • 1,401