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.

  • 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
    @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