Nuclear norm as minimum of Frobenius norm product 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?
 A: Here's a nice to way to go about this. I will write $\|\cdot\|_1$ for the nuclear norm, and $\|\cdot\|_2$ for the Frobenius norm.
First, we have the matrix Hölder inequality, which implies $\|UV\|_1\leq\|U\|_2\|V\|_2$. We also have $\|U\|_2\|V\|_2 \leq \tfrac{1}{2}(\|U\|_2^2 + \|V\|_2^2)$. Taken together, these give
$$
\|X\|_1 \leq \min_{UV = X} \|U\|_2 \|V\|_2 \leq \min_{UV = X} \tfrac{1}{2}(\|U\|_2^2 + \|V\|_2^2).
$$
To see that both inequalities are tight, let $X = S(X^*X)^{1/2}$ be the polar decomposition of $X$, with a partial isometry $S$ such that $S^*S$ is the support projection of $X^*X$. Taking $U = S(X^*X)^{1/4}$ and $V = (X^*X)^{1/4}$ works, since
$$
\|S(X^*X)^{1/4}\|_2^2 = \|(X^*X)^{1/4}\|_2^2 = \mathrm{tr}((X^*X)^{1/2}) = \|X\|_1,
$$
where the first step also uses that $S^*S$ is the support projection of $X^*X$.
One of the advantages of this more abstract argument over a brute-force calculation is that this argument also applies in any von Neumann algebras equipped with a normal semifinite trace. Therefore the equations are still valid in that context.
A: 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.
