11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – J. M. May 14 '13 at 18:10
  • $\begingroup$ 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. $\endgroup$ – Damien May 15 '13 at 6:30
8
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.