I want to calculate

$ f_{\mathbf x}(x_1,\ldots,x_k)\, = \frac{1}{(2\pi)^{k/2}|\boldsymbol\Sigma|^{1/2}} \exp\left(-\frac{1}{2}({\mathbf x}-{\boldsymbol\mu})^T{\boldsymbol\Sigma}^{-1}({\mathbf x}-{\boldsymbol\mu}) \right), $

for a huge ($k$ up 100.000) multivariate Gaussian distribution where $\boldsymbol\Sigma$ is sparse. Cholesky decomposition works fine if the $k$ is smallish and has the advantage that the determinant can be calculated easily from the factors. For larger $k$ I would like to use CG (conjugate gradient optimization), which is really fast to compute $({\mathbf x}-{\boldsymbol\mu})^T{\boldsymbol\Sigma}^{-1}({\mathbf x}-{\boldsymbol\mu})$, however I still need the determinant and have no idea how to (efficiently) compute or approximate it.

Are there any algorithms designed for this problem?

Thank you!


  • $\begingroup$ since the determinant is just for normalization, you should not need it if you use this distrubution to compute expectation values; and by the way, what is CG? $\endgroup$ – Carlo Beenakker Dec 15 '12 at 17:58
  • $\begingroup$ @Carlos CG: Conjugate gradient optimization (I modified my question accordingly). You are right, the mean, median, variance, covariance are trivial to "compute". Unfortunately I need the density. $\endgroup$ – Manuel Schmidt Dec 17 '12 at 5:57
  • $\begingroup$ For what do you need the density? If this is for maximum likelihood estimation, did you consider to use composite likelihood instead? $\endgroup$ – kjetil b halvorsen Dec 17 '12 at 17:08

Here are a few references that should help you get started in the area of approximating determinants:

Approximation of the determinant of large sparse symmetric positive definite matrices

Determinant Approximations

Matrices, Moments and Quadrature


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.