Computation of Cholesky factor

Question

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.

Answer 1

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.

Answer 2

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