Nuclear, or trace, or Ky Fan, norm of a matrix is defined as the sum of the singular values of the matrix.


It is claimed that
$$
\|X\|\_\sigma = \min\_{UV^T=X} \|U\|\|V\| = \min\_{UV^T=X} \frac{1}{2}(\|U\|^2 + \|V\|^2)
$$
where $\|\cdot\|\_\sigma$ is the nuclear norm of $X$ and $\|\cdot\|$ is the Frobenius norm.


What is the proof?



Nuclear norm as minimum of Frobenius norm product
We establish the following manifestation of the Cauchy-Schwartz inequality.
\begin{align}
\text{tr}(CD)&=\sum\_{ij}C\_{ij}D\_{ji} \\
&\le\Big(\sum\_{ij}C\_{ij}^2\Big)^\frac12\Big(\sum\_{ij}D\_{ij}^2\Big)^\frac12 \\
&=\big(\text{tr}(C^TC)\big)^\frac12\big(\text{tr}(D^TD)\big)^\frac12=\|C\|\|D\|,
\end{align}
for any real square matrices $C$ and $D$.


Perform the singular value decomposition of $X=ASB^T$ where $S$ is the diagonal matrix of the singular values of $X$ and $A$ and $B$ are the associated orthogonal matrices. Apply the above proposition, we have for any pairs of matrices $(U,V)\ni UV^T=X$
$$
\|X\|\_\sigma = \text{tr}(S) = \text{tr}(A^TUV^TB)\le \|A^TU\|\|V^TB\|=\|U\|\|V\|\le \frac12(\|U\|^2+\|V\|^2).
$$
The first inequality comes from the Cauchy-Schwarz inequality and the second from the squaring a sum. The equalities are achieved when $U=A\sqrt S$ and $V=B\sqrt S$.


We obtain the desired result.


