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!

  • 1
    $\begingroup$ 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. $\endgroup$
    – whuber
    Commented May 31, 2019 at 20:20
  • $\begingroup$ @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$ $\endgroup$ Commented May 31, 2019 at 21:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – whuber
    Commented May 31, 2019 at 21:43
  • $\begingroup$ @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?:) $\endgroup$ Commented May 31, 2019 at 22:39


Your Answer

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

Browse other questions tagged or ask your own question.