MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Lemma 1 in this paper: 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?

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
This only proves one direction (that LHS $\geq$ RHS), but not that the LHS $\leq$ RHS. – Yisong Yue Dec 20 '12 at 20:50
Oh I see now. Thanks for elaborating! – Yisong Yue Dec 20 '12 at 23:56
不 客 气。 互 相 帮 忙。^_^ – Betrand Dec 21 '12 at 1:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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