Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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? –  Carlo Beenakker Dec 15 '12 at 17:58
    
@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. –  Manuel Schmidt Dec 17 '12 at 5:57
    
For what do you need the density? If this is for maximum likelihood estimation, did you consider to use composite likelihood instead? –  kjetil b halvorsen Dec 17 '12 at 17:08

1 Answer 1

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

share|improve this answer
    
Thank you for the links. They might be helpful. –  Manuel Schmidt Dec 20 '12 at 6:17

Your Answer

 
discard

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

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