1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I think you should have put "the RHS is larger than or equal to the LHS". $\endgroup$
    – Betrand
    Dec 20, 2012 at 20:36
  • $\begingroup$ 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. $\endgroup$
    – Yisong Yue
    Dec 20, 2012 at 20:52

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.