Question

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?

Answer 1

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.