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

Solution 1:

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.