13
$\begingroup$

Let $$f(K) = \| K \|_*$$ be the nuclear norm (sum of the singular values) of $K=U\Sigma V^T$. How can one compute the subdifferential $\partial f$?

This may be a basic question, I'm trying to work my way through a paper in which minimizing $f$ over a convex set of matrices plays a central role. For what it's worth, I have found papers that display the end result, but not the derivation.

EDIT: This paper by Tao and Candes derives an expression, but refers the proof to "Characterization of the subdifferential of some matrix norms" which does not prove it as far as I can tell. I also found a class homework assignment posted online that said this was easy to "grind out" with matrix derivatives, but that there was another way via projections. Any guidance would be greatly appreciated.

Improve this question
$\endgroup$
8
$\begingroup$

Contrary to my first impression, this question is answered completely and thoroughly by G.A. Watson in Characterization of the Subdifferential of Some Matrix Norms. For the final derivation, see pg. 40.

The conclusion is that

$$\partial \|K\|_* = \left\{ UV^T+W:\ \ \ \|W\|<1, \text{columnspace}(U) \perp W\perp\text{ rowspace(V)} \right\},$$

where $\|\cdot\|$ is the spectral norm, which is dual to the nuclear norm.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ It should be $\|W\| \le 1$. $\endgroup$ – gerw Sep 26 '18 at 6:19
5
$\begingroup$

This is rather a comment, but a little bit longer.

There is a nice characterization of the subdifferentials of norms: If $X$ is a normed space, we have $$ \partial \|\cdot\| (x) = \{ x^* \in X^* : \|x^*\|_{X^*} \le 1 \text{ and } \langle x^*, x\rangle = \|x\|_X\}, $$ where $X^*$ is the topological dual of $X$ (and $\|\cdot\|_{X^*}$ is the dual norm).

I can't find a reference about the dual of your nuclear norm, but maybe this comment helps.

Improve this answer
$\endgroup$
  • $\begingroup$ If you can derive this characterization I would be pleased to accept this as an answer. I have also seen the subdifferential characterized as $UV^T+W$ where $||W||<1$. But no proof of either one! $\endgroup$ – Lepidopterist Apr 9 '13 at 22:16
  • $\begingroup$ The dual norm $\|\cdot\|_*$ should be the "maximal singular value"-norm. To prove it, one may use $$\|A\|_* = \max_{\|B\|=1} \mathrm{trace}(A^\top B).$$ Use the SVD of $A = U_A \, \Sigma_A \, V_A^\top$ and write $B = U_A \, \tilde B \, V_A^\top$. Then, $\|B\| = \| \tilde B\|$, and hence $$\|A\|_* = \max_{\|\tilde B\|=1} \mathrm{trace}(\Sigma_A \, \tilde B).$$ This should help to derive the dual norm. $\endgroup$ – gerw Apr 10 '13 at 6:23
  • $\begingroup$ Thanks gerw, but this is not my difficulty. I know that the dual norm of the nuclear norm is the operator norm, but I don't know how to derive your characterization of norm subdifferentials. $\endgroup$ – Lepidopterist Apr 10 '13 at 20:44
  • $\begingroup$ i will post the proof soon, i've basically got it. $\endgroup$ – Lepidopterist Apr 11 '13 at 2:49
  • $\begingroup$ @gerw In your expression for the subgradient of a generic norm, perhaps you meant <x*,x> <= ||x||_X? Otherwise I cannot see how it matches the expression in the special case of the nuclear norm ||.||_*. $\endgroup$ – gondolier Sep 25 '18 at 4:38

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.