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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Why do you say "low rank"? $\endgroup$
    – Igor Rivin
    Commented 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$
    – arbitUser1401
    Commented Mar 28, 2012 at 4:55

2 Answers 2

Reset to default
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.

Improve this answer
$\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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .