1. Let $\|M\| := \sigma_{max}(M)$, i.e. the spectral norm of $M$.
  2. $\langle X,Y \rangle = \text{Trace}(X^TY)$. Inner product of two matrices.

How to prove the title:

If $X = U\Sigma V^T$ and $\|Y\|=1$, why $Y = UV^T$ maximizes $\langle X,Y\rangle$

As a consequence:

  1. We know since $Y=UIV^T$, so $\sigma_{max}(Y) = 1$.
  2. Trace$(X^TY) = $trace$(\Sigma)$ = $\|X\|_*$, which is the nuclear norm.

The above is the key to prove that spectral norm and nuclear norm are dual.

(Also if you are interested in this proof, "Show that the dual norm of the spectral norm is the nuclear norm" is a good reference.)

Thank @angryavian. The proof is the following:

enter image description here

I met another problem: how to show the last two equalities?

  • 2
    $\begingroup$ I think this answer (which was linked in the comments of your link) answers this question. His $Q$ is your $Y$, and his $A$ is your $X$. $\endgroup$ – angryavian Sep 6 '16 at 0:36
  • 2
    $\begingroup$ It is a version of Procrustes' (or procrustean) Problem. $\endgroup$ – Jean Marie Sep 6 '16 at 1:06
  • $\begingroup$ Is $\mathrm X$ given? $\endgroup$ – Rodrigo de Azevedo Sep 7 '16 at 14:11
  • $\begingroup$ @RodrigodeAzevedo $X$ is given or not is not important. But yes $X$ is given since we know its SVD. $\endgroup$ – sleeve chen Sep 7 '16 at 22:02
  • 1
    $\begingroup$ @sleevechen You may want to take a look at math.stackexchange.com/q/1963711/339790 $\endgroup$ – Rodrigo de Azevedo Oct 11 '16 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.