Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'd like to draw a sample from a multivariate Gaussian distribution $\mathcal{N}(\mu, \Sigma)$, where $\mu$ is the mean vector (can assume it to be $\boldsymbol{0}$), and $\Sigma$ is a sparse positive definite covariance matrix. The standard way to draw a sample is to compute the Cholesky decomposition $\Sigma = L L^T$, draw a standard multivariate random normal $y \sim \mathcal{N}(\boldsymbol{0},I)$, then compute $x = Ly$ using e.g. back-substitution.

My question is as follows: I have a highly efficient black-box procedure for computing $\Sigma^{-1} y$ for arbitrary vectors $y$, but I do not have an efficient enough procedure for computing a Cholesky decomposition. Is it possible for me to efficiently draw a sample from this distribution? How?

share|cite|improve this question
How is $\mathbf \Sigma$ represented, and why are you unable to generate its Cholesky triangle? – J. M. Aug 1 '12 at 2:28
$\Sigma$ is a sparse matrix, and I am able to generate the Cholesky, but the computational cost is too high using standard algorithms. The relative cost of computing $\Sigma^{-1} y$ is much smaller by using the efficient black-box algorithm. – dan_x Aug 1 '12 at 2:35
This is too old to migrate, but you might want to delete and repost on Cross Validated – robjohn Jan 23 '13 at 16:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.