# Show that the dual norm of the spectral norm is the nuclear norm

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.

• 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. – Michael Grant Feb 21 '15 at 13:35
• @MichaelGrant so does this also implies that the dual norm of nuclear norm is spectral norm? – spatially Nov 3 '16 at 19:11
• That is correct. Norms always come in dual pairs. – Michael Grant Nov 4 '16 at 1:18

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.
• 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\}$? – Kristada673 Oct 1 '16 at 14:56