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?

`$U$`

and`$V$`

to be the sqrt of the singular value matrix times the left and right singular vectors achieves`$\|X\|_{\Sigma}$`

, so that proves that the RHS is less than or equal to the LHS. – Yisong Yue Dec 20 '12 at 20:52