# Computation of Cholesky factor

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.

• 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

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