Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

So the Cholesky decomposition theorem states that that any real symmetric positive-definite matrix $M$ has a Cholesky decomposition $M= LL^\top$ where $L$ is a lower triangular matrix.

Given $M$, we already know there are fast algorithms to calculate its Cholesky factor $L$.

Now, suppose I was given a rectangular $m\times n$ matrix $A$, and I knew that $A^\top A$ was positive definite. Is there a way to calculate the Cholesky factor $L$ of $A^\top A$ without computing $A^\top A$ explicitly and then applying Cholesky factorization algorithms?

If $A$ is a very large rectangular matrix performing $A^\top A$ explicitly seems very expensive and hence the question.

share|improve this question
    
More than the expense of forming the cross-product matrix, this approach also squares the condition number of your $\mathbf A$. If your $\mathbf A$ is nearly rank-deficient, then this is certainly a poor way to proceed. –  J. M. May 14 '13 at 18:10
    
This question and this question asks the same thing in different ways. The answers in these threads (and the answers below) should be useful to you. –  Damien May 15 '13 at 6:30

2 Answers 2

up vote 8 down vote accepted

Yes, you can obtain the factor (up to the signs of entries) using QR decomposition; see this answer. Note that if all you're interested in is solving the least squares problem that lead to the normal equations involving $A^T A$, you can use the QR decomposition directly.

share|improve this answer

Yes. Compute the $QR$ factorization and take $L=R^T$; rescale the rows of $R$ if necessary (by changing some of their signs) to make the sign of the diagonal nonnegative (as the Cholesky factor is defined to have a nonnegative diagonal).

For sparse QR factorizations see, e.g., http://dl.acm.org/citation.cfm?id=174408

share|improve this answer

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.