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.

$\endgroup$
0

2 Answers 2

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.

$\endgroup$
1
  • 4
    $\begingroup$ It should be $\|W\| \le 1$. $\endgroup$
    – gerw
    Sep 26, 2018 at 6:19
6
$\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.

$\endgroup$
6
  • $\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$ Apr 9, 2013 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, 2013 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$ Apr 10, 2013 at 20:44
  • $\begingroup$ i will post the proof soon, i've basically got it. $\endgroup$ Apr 11, 2013 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, 2018 at 4:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .