# Symmetric decomposition of a covariance matrix that is not given explicitly

I am implementing a Monte-Carlo method that requires decomposition of a $$k \times k$$ covariance matrix $$\Sigma=A^TA$$ where the dimensionality of $$A$$ should also be $$k\times k$$. No further constraints are on the properties of $$A$$ except for $$A\in \mathbb R$$.

At this moment, $$\Sigma$$ is unknown but I have a $$n\times k$$ ($$n\gg k$$) data matrix $$X$$ (column means 0) whose column-wise covariances equal $$\Sigma$$. I am seeking a method that would give me an $$A$$ without computing $$\Sigma$$.

One option is to decompose $$X=U\Sigma^\prime V^T$$ via singular value decomposition (SVD) and let $$A$$ be the first $$k$$ rows of $$\Sigma^\prime V^T$$.

Is there any computationally faster method than SVD to generate an $$A$$?

Thank you!

• The limitation not to compute $\Sigma$ looks artificial in this context, because the calculation of $\Sigma$ already is much faster than the calculation of the SVD of $X.$ Moreoever, if you do (miraculously) find an even more efficient way to obtain $A,$ then obtaining $\Sigma$ afterwards is nearly instantaneous, indicating you're not going to avoid doing at least as much work (asymptotically in $n$) as involved in computing $\Sigma$ anyway.
– whuber
Commented May 31, 2019 at 20:20
• @whuber Thank you for the comment. I have not compared the time costs but you might be right. I had this impression that the reason for PCA prefers SVD of the data matrix than eigendecomposition of the covariance matrix is because the covariances are really computationally demanding given $n\gg k$. Now after refreshing my memory I know it is also related to numerical stability and the non-negligible time for eigendecomposition itself. As for your 2nd point, in this simulation I would never need the covariance matrix $\Sigma$ Commented May 31, 2019 at 21:19
• Understood: the idea was to show that asymptotically, because $n\gg k,$ there is nothing gained by avoiding the computation of $\Sigma.$ Thus, if the best route to computing $A$ goes through $\Sigma,$ don't hamstring yourself by precluding that option.
– whuber
Commented May 31, 2019 at 21:43
• @whuber Thank you for the advice. One last question, say I take the route of computing covariances to get some $A$, what is the fastest decomposition technique out there? I can do Cholesky decomposition if $\Sigma$ is also positive definite, and can retreat to eigendecomposition otherwise. Do you happen to know any faster method?:) Commented May 31, 2019 at 22:39