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.