1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What does the subscript $F$ stand for? $\endgroup$ – uniquesolution Mar 5 '17 at 11:55
  • $\begingroup$ @uniquesolution Its frobenius norm; I have made an edit $\endgroup$ – wf34 Mar 5 '17 at 11:59
2
$\begingroup$

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)$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.