Finding $X$ When $Y=XX'$

Consider matrices $Y\in\mathbb{R}^{n\times n}$ and $X\in\mathbb{R}^{n\times m}$ where $m\geq n$. $X$ is unknown but $Y=XX'$, which implies that $Y$ is positive definite (I see no reason why this couldn't alternately be expressed as a positive semi-definite problem with $Y=X'X$, a different $Y\in\mathbb{R}^{m\times m}$ would still be known).

What the easiest method to find $X$? I was thinking of minimizing the Frobenius norm, but wasn't sure if there was some relatively straightforward thing that I'm missing.

-
Notice the typographical difference between $Y\epsilon\mathbb{R}^{n\times n}$ and $Y\in\mathbb{R}^{n\times n}$. Writing \in rather than \epsilon not only makes the symbol look different, but also results in proper spacing, since those conventions are built in to the software. $\TeX$ is fairly sophisticated. (I changed it in the posting.) – Michael Hardy Sep 11 '12 at 22:20
When I see epsilon, I think of Hilbert choice operator, but of course the arity is different.. – user2468 Sep 11 '12 at 22:24
@MichaelHardy Thanks. – John Sep 12 '12 at 2:53

Consider $X = I$, then $X' = I$ and $Y = I$. On the other hand, if $X = -I$, then $X' = -I$, but $Y = I$ still. Are there any other assumptions you can make about $X$?

In fact, for any $X$, $(-X)(-X)' = XX'$, so there are always at least two solutions.

Additionally, if $$X_1 = \left(\begin{array}{cc} a_1 & b_1 \\ 0 & 0\end{array}\right),\quad X_2 = \left(\begin{array}{cc} a_2 & b_2 \\ 0 & 0\end{array}\right)$$

with $a_1^2 + b_1^2 = a_2^2 + b_2^2$ then $Y = X_1 X_1' = X_2 X_2'$.

I think maybe something needs to be said about the singular values of $X$ to get better uniqueness - maybe that they're all non-degenerate?

-
$Y$ is some known matrix. It could be an identity matrix, or it could be anything else so long as it is positive definite. – John Sep 11 '12 at 21:39
Ok, but what I'm saying is that there might not be a unique $X$ such that $Y = XX'$, unless we can make some more assumptions (or unless uniqueness isn't a concern). – BaronVT Sep 11 '12 at 22:14
I think the non-uniqueness can get worse than this also - see the edit to my answer. – BaronVT Sep 11 '12 at 22:49
For any orthogonal matrix $R$, if $X$ satisfies $X X' = Y$ then so does $X R$. So there's always a lot of non-uniqueness. – Robert Israel Sep 12 '12 at 1:22
In fact, if $n=m$ and $Y$ is invertible, that's all the non-uniqueness there is: if $X X' = Z Z' = Y$ is invertible, then $Z$ and $Z'$ are invertible and $Z^{-1} X (Z^{-1} X)' = Z^{-1} X X' (Z')^{-1} = Z^{-1} Z Z' (Z')^{-1} = I$ so $Z^{-1} X$ is orthogonal, i.e. $X = Z R$ for an orthogonal matrix $R$. – Robert Israel Sep 12 '12 at 1:30

You also need $Y$ to be symmetric. An algorithm which does this if you want $X$ to be triangular is the Cholesky decomposition.

-
You might need full pivoting if the matrix is singular. ($Y = XX'$ already implies $Y$ is symmetric.) – Tunococ Sep 11 '12 at 23:42