Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given matrices $C\in \mathbb{R}^{n\times k}$ and $X\in \mathbb{R}^{n\times k}$, it is known that $X$ minimizes the following

$$\|CC^T-XX^T\|_F^2$$

Can it be proved that such solution X minimizes

$$\|C-X\|_F^2$$

Note that $\|\cdot\|_F$ corresponds to the Frobenius norm.

Edit

The question is as I posted it primarily. Note that the dimensions of $C$ and $X$ need to be the same; otherwise $\|C-X\|^2$ would not be possible. With your $X=CU$, what is obtained is $\|CC^T-CC^T\|$. Note that one could trivially set $X=C$ to annihilate Frobenius norm, but that's not the point. Matrix $X$ is supplied externally, and it is known that it minimizes $\|CC^T-XX^T\|^2$; question is: does it also minimize $\|C-X\|^2$?

In the external algorithm, matrix $X$ is obtained as $X=Lsv(C)SV(C)^{1/2}$, where $Lsv(C)$ denotes left-singular vector of $C$, and $SV(C)^{1/2}$ a diagonal matrix with roots of singular values of C. Note that $||C−X||^2$ does not need to be 0 to be minimal.

share|improve this question

migrated from stackoverflow.com Jan 31 '12 at 16:13

This question came from our site for professional and enthusiast programmers.

2  
Did you maybe mean: $X\in \mathbb R^{k\times n}$ minimizes $\Vert CC^T - X^TX\Vert_F^2$ (or something to that effect)? If not: consider for example $X = CU$ with $UU^T = 1$. –  Sam Jan 31 '12 at 16:29
    
I edited the question to include some updates that user506901 posted as an answer (now deleted). @user506901: please register your account and/or associate it to your SO one. After that we can see if the stack team can associate this question to your account so that you can edit the question yourself. –  Willie Wong Feb 1 '12 at 14:24
    
But in this case your matrix $X$ probably has to suffice some additional criteria. As otherwise you could just take $X=C$, which makes both norms $0$, the most minimal minimum that can be achieved. So like Sam said, not every $X$ that minimizes the first equation needs to minimize the second. But we need to know the constraints imposed on $X$ (by the external algorithm or whatever), as I guess you cannot just set $X=C$. –  Christian Rau Feb 1 '12 at 14:36

1 Answer 1

up vote 3 down vote accepted

My comment above (consider $X = CU$ with $UU^T=1$) was meant like this:

Any such $X$ minimizes your first norm, since $\|CC^T - XX^T\| = 0$, but

$$\|C - X\| = \|C(1-U)\| \ne 0$$

if $U\ne 1$ (at least in general). So not all matrices minimizing the first expression will also minimize the second.

share|improve this answer
    
In the external algorithm, matrix $X$ is obtained as $X=Lsv(C)SV(C)^{1/2}$, where $Lsv(C)$ denotes left-singular vector of $C$, and $SV(C)^{1/2}$ a diagonal matrix with roots of singular values of $C$. Note that $||C-X||^2$ does not need to be 0 to be minimal. –  user506901 Feb 1 '12 at 15:32
1  
@user506901 Aah! So that's what's missing from your question. Now add it in, as otherwise Sam's answer in the correct one, of course. –  Christian Rau Feb 1 '12 at 16:17
    
@user506901 As Christian has already written in two comments: you should add this additional information to your question. I partially wrote this answer, because I suspected you might write your assumptions on $X$ as a comment to it (as you did). And my crystal ball is broken at the moment. ;) –  Sam Feb 1 '12 at 20:30

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.