12

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.

J. M.
  • 3,155
  • 28
  • 37
smilingbuddha
  • 645
  • 5
  • 10
  • 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 06:30

2 Answers2

9

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.

Community
  • 1
Christian Clason
  • 12,301
  • 3
  • 48
  • 68
8

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

Arnold Neumaier
  • 11,318
  • 20
  • 47