# Low rank Matrix factorization

Hello,

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)

Thanks

-
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

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.

-