Skip to main content
MathOverflow

Return to Question

explain that I mean relative accuracy, not additive.
Source Link
Daniel Soudry
Daniel Soudry
  • 978
  • 5
  • 16

Suppose you have a general $n$-th dimensional random Gaussian vector with probability distribution function $\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right)$. What is the computational complexity (both space or time) of calculating the cumulative distribution function

$\int_{-\infty}^{y_1}dx_{1}\cdots\int_{-\infty}^{y_n}dx_{n}\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right) $

?

This should be a function of $n$. If the suggested integration method is approximate (e.g., using monte-carlo methods), then the complexity may also depend on some required mean relative accuracy (std/mean) $\epsilon$.

Thanks in advance!

Suppose you have a general $n$-th dimensional random Gaussian vector with probability distribution function $\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right)$. What is the computational complexity (both space or time) of calculating the cumulative distribution function

$\int_{-\infty}^{y_1}dx_{1}\cdots\int_{-\infty}^{y_n}dx_{n}\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right) $

?

This should be a function of $n$. If the suggested integration method is approximate (e.g., using monte-carlo methods), then the complexity may also depend on some required mean accuracy $\epsilon$.

Thanks in advance!

Suppose you have a general $n$-th dimensional random Gaussian vector with probability distribution function $\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right)$. What is the computational complexity (both space or time) of calculating the cumulative distribution function

$\int_{-\infty}^{y_1}dx_{1}\cdots\int_{-\infty}^{y_n}dx_{n}\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right) $

?

This should be a function of $n$. If the suggested integration method is approximate (e.g., using monte-carlo methods), then the complexity may also depend on some required mean relative accuracy (std/mean) $\epsilon$.

Thanks in advance!

added 3 characters in body
Source Link
Daniel Soudry
Daniel Soudry
  • 978
  • 5
  • 16

Suppose you have a general $n$-th dimensional random Gaussian vector with probability distribution function $\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right)$. What is the computational complexity (both space or time) of calculating the cumulative distribution function

$\int_{-\infty}^{y_1}dx_{1}\cdots\int_{-\infty}^{y_n}dx_{n}\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right) $

?

This should be a function of $n$. If the suggested integration method is approximate (e.g., using monte-carlo methods), then the complexity may also depend on some required mean accuracy $\epsilon$.

Thanks in advance!

Suppose you have a general $n$-th dimensional random Gaussian vector with probability distribution function $\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right)$. What is the computational complexity (both space or time) of calculating the cumulative distribution function

$\int_{-\infty}^{y_1}dx_{1}\cdots\int_{-\infty}^{y_n}dx_{n}\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right) $

?

This should a function of $n$. If the suggested integration method is approximate (e.g., using monte-carlo methods), then the complexity may also depend on some required mean accuracy $\epsilon$.

Thanks in advance!

Suppose you have a general $n$-th dimensional random Gaussian vector with probability distribution function $\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right)$. What is the computational complexity (both space or time) of calculating the cumulative distribution function

$\int_{-\infty}^{y_1}dx_{1}\cdots\int_{-\infty}^{y_n}dx_{n}\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right) $

?

This should be a function of $n$. If the suggested integration method is approximate (e.g., using monte-carlo methods), then the complexity may also depend on some required mean accuracy $\epsilon$.

Thanks in advance!

Source Link
Daniel Soudry
Daniel Soudry
  • 978
  • 5
  • 16

Computation complexity of calculating the cdf of an n-th dimensional gaussian random vector

Suppose you have a general $n$-th dimensional random Gaussian vector with probability distribution function $\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right)$. What is the computational complexity (both space or time) of calculating the cumulative distribution function

$\int_{-\infty}^{y_1}dx_{1}\cdots\int_{-\infty}^{y_n}dx_{n}\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right) $

?

This should a function of $n$. If the suggested integration method is approximate (e.g., using monte-carlo methods), then the complexity may also depend on some required mean accuracy $\epsilon$.

Thanks in advance!