2
$\begingroup$

As we know that every norm is convex, and if a function is convex w.r.t. the input variable, then corresponding Hessian should be positive semidefinite. When I try to find the Hessian of Frobenius norm, I can't obtain expected result. I compute the Hessian as follows

I first compute the first order derivative: $\frac{\partial \||X\||_F^2}{\partial X} = 2X$, and I refer to the Other matrix derivatives section in wiki http://en.wikipedia.org/wiki/Matrix_calculus to compute the $\frac{\partial 2X}{\partial X}$. However, it seems that if I use that formula, I won't get desired result.

Hope someone could tell me what is wrong with my derivation. Thanks very much.

$\endgroup$
4
$\begingroup$

When working with the Frobenius norm, we can stack the columns of $X$ into a single vector $\widehat X\in \mathbb R^{n^2}$ and take the norm of that. This simplifies the computation: the gradient is $2\widehat X$ and the Hessian is $2I$ where $I$ is the identity matrix acting on $\mathbb R^{n^2}$; i.e., the identity matrix of size $n^2\times n^2$.

If you insist on matrix notation for $X$, then notice that the derivative of $X\mapsto 2X$ with respect to $X$ does not naturally fit in a matrix form; matrix-by-matrix derivatives are absent from the table in the wiki article you mentioned.

Notice that we could also talk about the derivative of a vector with respect to a matrix, or any of the other unfilled cells in our table. However, these derivatives are most naturally organized in a tensor of rank higher than 2, so that they do not fit neatly into a matrix

You would need a tensor of order 4 to express the Hessian in this case.

$\endgroup$
  • $\begingroup$ Thanks for your replying. If we cannot use matrix to matrix form in the section - Other matrix derivative of wiki, why it places the formula there? $\endgroup$ – Charles Zheng Mar 13 '14 at 15:23
  • $\begingroup$ @Charles The wiki contains some formulas for this case, which it also criticizes. I don't mean to stop you from using them. You said that you don't get desired result from them. Please also keep in mind that Wikipedia is not a reliable source. $\endgroup$ – user127096 Mar 13 '14 at 15:34
5
$\begingroup$

More generally, consider $n\times n$ real matrices $A,X$ and the function $f:X\rightarrow ||AX||^2=trace(AXX^TA^T)$. Then its derivative is $D_Xf:H\rightarrow 2trace(X^TA^TAH)$. moreover its Hessian is $Hess_X(f):(H,K)\rightarrow 2trace(K^TA^TAH)$, a symmetric bilinear form that does not depend on $X$. Let $(E_{i,j})$ be the canonical basis of $M_n$. Then, if $j\not=l$, then $Hess_X(f)(E_{i,j},E_{k,l})=0$ and $Hess_X(f)(E_{i,j},E_{k,j})=2u_{i,k}$ where $u_{i,j}$ is the $(i,j)$ entry of $A^TA$.

Let $vec(U)$ denotes the vectorization of a $n\times n$ matrix $U$, formed by stacking the rows (resp. the columns) of $U$ into a single column vector. Then the $n^2\times n^2$ symmetric matrix associated to $Hess_X(f)$ is $2A^TA\otimes I_n$ (resp. $2I_n\otimes A^TA$). cf.:

http://en.wikipedia.org/wiki/Kronecker_product

The eigenvalues $(\lambda_i)_i$ of $A^TA$ are non-negative. The eigenvalues of $2A^TA\otimes I_n$ and $2I_n\otimes A^TA$ are $(2\lambda_i)_i$, $n$ times each ; hopefully, $Hess_X(f)$ is sym. non-negative (semidefinite). In particular, if $A=I_n$, then $Hess_X(f)$ is associated to the matrix $2I_n\otimes I_n=2I_{n^2}$ as 127 wrote above.

EDIT: Charles, that you write is the gradient $\nabla_X(f)=2A^TAX$. The gradient is defined from the matrix scalar product $(U,V)=trace(U^TV)$ by the formula $(\nabla_X(f),H)=D_Xf(H)$. We conclude by identification.

$\endgroup$
  • $\begingroup$ What do you mean by $D_xf: H \to 2trace(X^TA^TAH)$ ?, as the derivative of $f(X)$ should be $2A^TAX$. $\endgroup$ – Charles Zheng Mar 14 '14 at 4:58

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.