Could someone help me understand why the dual norm of the spectral norm is the nuclear norm?

We can focus on the real field. Given a matrix $X \in \mathbb{R}^{m \times n},$ then the spectral norm is defined by

$$\left \| X\right\| = \max\limits_{i \in \{1, \dots, \min\{m,n\}\} }\sigma_i (X)$$

whereas the nuclear norm is defined by

$$\left \| X \right \|_* = \sum\limits_{i=1}^ {\min\{m,n\}} \sigma_i (X)$$

Can someone show me the reasoning process? Thank you in advance.

  • $\begingroup$ Answered here: math.stackexchange.com/questions/1142540/… . The nuclear norm is proved to be convex my proving that it is the dual of the spectral norm. $\endgroup$ Feb 21 '15 at 13:35
  • $\begingroup$ @MichaelGrant so does this also implies that the dual norm of nuclear norm is spectral norm? $\endgroup$
    – spatially
    Nov 3 '16 at 19:11
  • $\begingroup$ That is correct. Norms always come in dual pairs. $\endgroup$ Nov 4 '16 at 1:18

I proved it here in a question about whether or not the nuclear norm is convex. I will reproduce the result here. If the mods see fit to close the question as a duplicate that's fine, but they may not since the question itself is different.

Recall that for any norm, the definition of the dual norm $\|\cdot\|_*$ is $$\|A\|_* = \sup_{\|Q\|\leq 1} \langle Q, A \rangle.$$ For the nuclear norm, $$\|Q\| \triangleq \sigma_1(Q), \quad \|A\|_* \triangleq \sum_i \sigma_i(A).$$ Therefore we seek to prove that $$\sup_{\sigma_1(Q)\leq 1} \langle Q, A \rangle = \sup_{\sigma_1(Q)\leq 1} \mathop{\textrm{Tr}}(Q^HA) = \sum_i \sigma_i(A).$$

We will first prove that $\sup_{\sigma_1(Q)\leq 1} \langle Q, A \rangle \geq \sum_i\sigma_i(A).$ Let $A=U\Sigma V^H=\sum_i \sigma_i u_i v_i^H$ be the singular value decomposition of $A$, and define $\bar{Q}=UV^H=UIV^H$. $\bar{Q}$ is unitary, so all of its singular values are 1, hence $\sigma_1(\bar{Q})=1$. And $$\langle \bar{Q}, A \rangle = \langle UV^H, U\Sigma V^H \rangle = \mathop{\textrm{Tr}}(VU^HU\Sigma V^H) = \mathop{\textrm{Tr}}(V^HVU^HU\Sigma) = \mathop{\textrm{Tr}}(\Sigma) = \sum_i \sigma_i.$$ (Note our use of the identity $\mathop{\textrm{Tr}}(ABC)=\mathop{\textrm{Tr}}(CAB)$; this is always true when both multiplications are well-posed.) Since the supremum cannot be smaller than this single instance, we have $$\sup_{\sigma_1(Q)\leq 1} \langle Q, A \rangle \geq \langle\bar{Q}, A \rangle = \sum_i \sigma_i(A).$$ Now let's prove the other direction: $$\sup_{\sigma_1(Q)\leq 1} \langle Q, A \rangle = \sup_{\sigma_1(Q)\leq 1} \mathop{\textrm{Tr}}(Q^HU\Sigma V^H) = \sup_{\sigma_1(Q)\leq 1} \mathop{\textrm{Tr}}(V^HQ^HU\Sigma) = \sup_{\sigma_1(Q)\leq 1} \langle UQV^H, \Sigma \rangle = \sup_{\sigma_1(Q)\leq 1} \sum_{i=1}^n \sigma_i (UQV^H)_{ii} = \sup_{\sigma_1(Q)\leq 1} \sum_{i=1}^n \sigma_i u_i Q v_i^H \leq \sup_{\sigma_1(Q)\leq 1} \sum_{i=1}^n \sigma_i \sigma_1(Q) = \sum_{i=1}^n \sigma_i. $$ The inequality comes from the fact that $\|u_i\|=\|v_i\|=1$, and $$u_i^H Q v_i \leq \sup_{\|u\|_2=\|v\|_2=1} u^HQv = \sigma_1(Q).$$ Therefore, $$\sup_{\sigma_1{Q}\leq 1} \langle Q, A \rangle \leq \sum_i \sigma_i(A).$$ We have proven both the $\leq$ and $\geq$ cases, so equality is confirmed.

  • 1
    $\begingroup$ Very insightful! Is it also true that $\sup_{\sigma_1{Q}\leq 1} \langle Q, A \rangle = \sup \left\{ Tr(Q^TA) \, | \, \|Q\|_2 \leq 1 \right\}$? $\endgroup$ Oct 1 '16 at 14:56
  • 1
    $\begingroup$ Yes the equality holds. They are one an the same object, written in different notations. $\endgroup$
    – dohmatob
    Oct 12 '16 at 8:55

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.