2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Note that you're computing the derivative of a matrix-valued function with respect to a matrix, so the form of your derivative will definitely be a bit strange. In particular, if we take the Frechet derivative, the output of the second derivative should be a linear transformation from matrices to matrices. To interpret $\frac {d^2}{dX^2}$ in the same way as you did with $\frac d{dX}$, you'd need a function that produces rank $4$ tensors. $\endgroup$ – Ben Grossmann Dec 21 '16 at 3:47
  • $\begingroup$ You might be better off forgetting about Newton and using a gradient-based method like Polak-Ribiere or Barzilai-Borwein. $\endgroup$ – greg Dec 21 '16 at 4:56
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

http://cvxr.com/tfocs/

Finally, specialists get tired of answering questions often without really being listened to; indeed, people prefer to reinvent the wheel...

$\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.