MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


I've a SPD matrix A; which needs to be factorized as ${A=SS^{T}}$. But, using Cholesky for this purpose is prohibitive in terms of computational cost. Moreover, matrix is Dense and has a slow decaying eigen-spectrum.

Can anything be suggested for replacement of cholesky. Moreover, it need not be exact,anything approximate will work as long as $y=Sz$ and the quantity $y^{T}y$ is what I'm trying to preserve.($z$ is standard normal vector)


share|cite|improve this question
Why do you say "low rank"? – Igor Rivin Mar 27 '12 at 1:31
Right now I'm trying using truncated SVD; (In general it need not be low rank) Sorry about the confusion – zimbra314 Mar 28 '12 at 4:55
up vote 1 down vote accepted

Sarlos and Clarkson and Woodruf give efficient streaming algorithms for the more general problem of computing an approximate singular value decomposition of an arbitrary matrix. Because of the sublinear space streaming constraints, they look at "tall" matrices: much fewer columns than rows. But the algorithm should work and give efficiency gains for square matrices as well. The idea is to project the columns onto a much smaller dimension, similarly to the proof of the Johnson-Lindenstraus lemma, and then work with this smaller matrix.

share|cite|improve this answer

Your Answer


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.