4
$\begingroup$

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.

  • 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$.2012-01-31
  • 0
    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.2012-02-01
  • 0
    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$.2012-02-01

1 Answers 1

3

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.

  • 0
    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.2012-02-01
  • 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.2012-02-01
  • 0
    @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. ;)2012-02-01