Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.