Prove that nuclear norm of a matrix is equal to the sum of squares of Frobenius norm

Question

Nuclear norm of a matrix is defined as the sum of the singular values of the matrix.

I saw a Lemma (without any proof) claiming

$$ \|X\|_\sigma = \min_{X=UV'} \|U\|\|V\| = \min_{X=UV'} \frac{1}{2}(\|U\|^2 + \|V\|^2) $$ where $\|.\|_\sigma$ is the nuclear norm of $X$ and $\|.\|$ is the Frobenius norm.

Where can I find the proof of this proposition?

Answer 1

This is a simple consequence of Cauchy-Schwarz inequality. Let $X=PSQ'$ be a singular value decomposition of $X$. If $UV'=X$, then $$ \|X\|_\sigma =\operatorname{tr}(S) =\operatorname{tr}(P'UV'Q) \le\|P'U\|_F\|Q'V\|_F =\|U\|_F\|V\|_F \le\frac12(\|U\|_F^2+\|V\|_F^2). $$ Since ties occur when $U=PS^{1/2}$ and $V=QS^{1/2}$, the conclusion follows.