Question

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

Answer 1

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.