1
$\begingroup$

I have a symmetric positive definite (SPD) matrix $A$ that needs to be factorized as ${A=SS^{T}}$. However, using the Cholesky decomposition for this purpose is prohibitive in terms of computational cost. Moreover, the 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 am trying to preserve, where $z$ is standard normal vector.

$\endgroup$
2
  • $\begingroup$ Why do you say "low rank"? $\endgroup$
    – Igor Rivin
    Mar 27, 2012 at 1:31
  • $\begingroup$ Right now I'm trying using truncated SVD; (In general it need not be low rank) Sorry about the confusion $\endgroup$ Mar 28, 2012 at 4:55

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

You could try to interpolate a dense matrix from a few columns and rows: http://dx.doi.org/10.1007/s006070070031 http://www.researchgate.net/publication/251735015_How_to_find_a_good_submatrix/file/e0b49527254918b220.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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