# Proof of Tracenorm Equality

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?

-
I think you should have put "the RHS is larger than or equal to the LHS". – Betrand Dec 20 '12 at 20:36
Choosing $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

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.
This only proves one direction (that LHS $\geq$ RHS), but not that the LHS $\leq$ RHS. – Yisong Yue Dec 20 '12 at 20:50