Lemma 1 in this paper: <http://ttic.uchicago.edu/~nati/Publications/SrebroShraibmanCOLT05.pdf> claims that


$\|X\|\_{\Sigma} = \min\_{V^TU=X} \frac{1}{2}(\|U\|\_{Fro}^2 + \|V\|\_{Fro}^2),$


where $\|X\|\_{\Sigma}$ denotes the tracenorm and $\|U\|\_{Fro}$ denotes the Forbenius norm. $U$ and $V$ are assumed to be of sufficiently high rank. Proving one direction is easy (that the RHS is less than or equal to the LHS). Can anyone provide a proof of the other direction?



Proof of Tracenorm Equality
Let $X=W\_1^T\Sigma W\_2$ be the singular value decomposition of $X$, where $W\_1, W\_2$ are unitaries and $\Sigma$ diagonal matrix. Taking $V=\sqrt{\Sigma}W\_1$, $U=\sqrt{\Sigma}W\_2$, the minimum is achieved. 


I am not sure whether I understand your comment correctly. The other direction is easy, $\|X\|\_1=\|V^TU\|\_1\le \|V\|\_2\|U\|\_2\le (\|V\|\_2^2+\|U\|\_2^2)/2$, where $\|\cdot\|\_1$, $\|\cdot\|\_2$ denote trace norm, Frobenius norm, respectively. The first inequality follows from log majorization for singular values, the second one is by AM-GM inequality.


