# Minimizing the matrix norm, equivalence

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.

-
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

## migrated from stackoverflow.comJan 31 '12 at 16:13

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