Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
The nuclear norm is defined in the following way
$$\| X \|_* := \mbox{tr} \left( \sqrt{X^T X} \right)$$
and, from Derivative of the nuclear norm with respect to its argument,
$$\frac{d}{dX} \| X \|_* = U\Sigma^{-1}\mid\Sigma \mid V^T$$
What is the second derivative of the nuclear norm?
$$\frac{d^2}{dX^2} \| X \|_* = ?$$
I need it to compute Newton's method for my algorithm and I haven't had much success. Any help would greatly be appreciated. Thanks in advance!
The reason you haven't had any success is that the nuclear norm is not differentiable. Your answer for the derivative is only partly correct. If you are in the positive definite cone your answer is correct and reduces to the identity matrix $I$, but if the matrix $X$ is low rank then the function is not differentiable and the best you can do is to compute the sub-differential $$ \partial \|X\|_* = \left\{UV^\top+W: U^TW = WV = 0, \quad\|W\|_2\right\}, $$ where $\|W\|_2=\max eig(W)$ is the spectral norm which is the maximum eigenvalue of W.
Since the nuclear norm is a norm and all norms are convex we can talk about the sub-differential which is the set of all tangents that lie below the function. The proof of the result above can be found in this paper:
Watson, G. A. Characterization of the subdifferential of some matrix norms. Linear Algebra and its Applications, 170:33– 45, 1992.
From the expression above you can see that the nuclear norm is piecewise linear on each of the cones. The second derivative would therefore be zero on each of the differentiable pieces. That should explain why Newton's algorithm doesn't work so well (actually it depends on what else is in your objective function Another way to look at it is that all norms look like $|x|$ when you take one dimensional slices, and $|x|$ is piecewise linear with second derivative 0 except for at $x=0$ where it is not differentiable.
If you really want to use Newton's approach you should use the variational formulation that says that $$ \|X\|_* = \min_{L,R:LR^\top = X} \frac{1}{2}\left(\|L\|_F^2+\|R\|_F^2\right) $$ then minimizing a function like $$ f(X)+\|X\|_* = \min_{L,R} f(LR^\top)+ \frac{1}{2}\left(\|L\|_F^2+\|R\|_F^2\right) $$ can be done by alternating minimization over $L$ and $R$, where these problems are continuous if $f$ is continuous.
Assume that $n\geq p$. Let $\phi:X\in M_{n,p}\rightarrow ||X||_*$; then $\phi$ is $C^{\infty}$ in a neighborhood of any $X\in M_{n,p}$ that has full rank $p$.
Let $f:A\in S_p^{>0}\rightarrow tr(\sqrt{A})$; then $Df_A:L\in S_p\rightarrow 1/2tr(LA^{-1/2})$.
According to my post or that of greg in (1)
Derivative of the nuclear norm with respect to its argument
The derivative of $\phi$ is $D\phi_X:H\in M_{n,p}\rightarrow tr(X(X^TX)^{-1/2}H^T)$.
Unfortunately, there is no such closed form for $D^2\phi_X(H,K)$, because, in general, $X^TX$ and $(X^TX)'$ do not commute (that is useless for the calculation of the first derivative).
On the other hand, that is above does not work when $X$ has not full rank. Since the norms are all equivalent, I do not understand why researchers persist in using the nuclear norm instead of the standard Frobenius norm. Something escapes my mind but the specialists surely have good reasons.
About alternative methods, Peder gave here an interesting answer concerning the sub-differential. Moreover, Michael Grant in (1) again, speaks about several methods that seem to give a good answer to the OP's question; the last but not the least, Michael gives a link to his software TFOCS
Finally, specialists get tired of answering questions often without really being listened to; indeed, people prefer to reinvent the wheel...
