According to [1], [2] and other related publications, the following holds for any matrix $X$:
$$\| X\|_\Sigma=\min_{X=UV'}\|U\|_\mathrm{Fro}\|V\|_\mathrm{Fro}=\min_{X=UV'}\frac{1}{2}(\|U\|_\mathrm{Fro}^{2}+\|V\|_\mathrm{Fro}^2)$$
where $\|\cdot\|_\Sigma$ is the trace (nuclear/Ky-Fan) norm and $\|\cdot\|_\mathrm{Fro}$ is the Frobenius norm.
Can anyone show why this equality is true?
In the publications, it is filed under "Preliminaries" and one of the few Lemmas without proof. I find this relationship very fundamental and interesting, but could not find it anywhere else, let alone proof.
Thank you for any help!
What I already have:
If I understand the 'hint' in ref. 1 (above) correctly, $\min_{X=UV'}\|U\|_\mathrm{Fro}\|V\|_\mathrm{Fro}$ is minimized by $U=\hat{U}\sqrt{\Lambda}$ and $V=\hat{V}\sqrt{\Lambda}$, where $X=\hat{U}\Lambda \hat{V'}$ is the singlular value decomposition of $X$ (Page 75, Lemma 8 in ref. 1 (above)).
Best Answer
2nd equality: the $\le$ is just AM-GM inequality. To get $=$, replace $U$ by $\lambda U$ and $V$ by $\lambda^{-1}V$ so that the norms of $U$ and $V$ become the same.
1st equality: the hint tells you how to get $\ge$. So suppose that $X = UV$. Let the singular decomposition of $X = Q \Lambda P^*$, where $Q$ and $P$ are unitary, and $\Lambda$ is diagonal with non-negative entries. Then $\Lambda = Q^* U V P$, and so $$\|X\|_\Sigma = \text{trace}(\Lambda) \le \|Q^* U\|_F \|V P\|_F = \|U\|_F \|V\|_F .$$