Sampling Complexity of Multivariate Normal Distribution

Question

What is the computational complexity of sampling from a multivariate normal distribution ?

Does the covariance matrix need to be inverted first, yielding a O(n^3) algorithm or there exists algorithms with complexity O(n^2) ?

Answer 1

If C is your covariance matrix, and C=LL^T is its Cholesky decomposition, then Lx would have the required covariance structure. Here, x is an n-vector of standard normal variables.

Cholesky decomposition takes O(n^3) time to compute. However, if you do it upfront and then just use L, you'll have amortized the cost across all the random samples you compute.