1
$\begingroup$

Hi,

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!

Manuel

Improve this question
$\endgroup$
3
  • $\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
    Commented Dec 15, 2012 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
    Commented Dec 17, 2012 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
    Commented Dec 17, 2012 at 17:08

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .