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.

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.

share|improve this question
1  
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
add comment

2 Answers

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?

share|improve this answer
    
$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
1  
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
1  
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
show 3 more comments

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

share|improve this answer
    
You might need full pivoting if the matrix is singular. ($Y = XX'$ already implies $Y$ is symmetric.) –  Tunococ Sep 11 '12 at 23:42
add comment

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.