O(N) Hierarchical algorithm for computing the expectations of truncated multi-variate normal distributions in N dimensions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2018
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912753633984512 |
|---|---|
| author | Huang, Jingfang Fang, Fuhui Turkiyyah, George Cao, Jian Genton, Marc G. Keyes, David E. |
| author_facet | Huang, Jingfang Fang, Fuhui Turkiyyah, George Cao, Jian Genton, Marc G. Keyes, David E. |
| contents | In this paper, we study the $N$-dimensional integral $ϕ(a,b; A) = \int_{a}^{b} H(x) f(x | A) \text{d} x$ representing the expectation of a function $H(X)$ where $f(x | A)$ is the truncated multi-variate normal (TMVN) distribution with zero mean, $x$ is the vector of integration variables for the $N$-dimensional random vector $X$, $A$ is the inverse of the covariance matrix $Σ$, and $a$ and $b$ are constant vectors. We present a new hierarchical algorithm which can evaluate $ϕ(a,b; A)$ using asymptotically optimal $O(N)$ operations when $A$ has "low-rank" blocks with "low-dimensional" features and $H(x)$ is "low-rank". We demonstrate the divide-and-conquer idea when $A$ is a symmetric positive definite tridiagonal matrix, and present the necessary building blocks and rigorous potential theory based algorithm analysis when $A$ is given by the exponential covariance model. Numerical results are presented to demonstrate the algorithm accuracy and efficiency for these two cases. We also briefly discuss how the algorithm can be generalized to a wider class of covariance models and its limitations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1809_08315 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | O(N) Hierarchical algorithm for computing the expectations of truncated multi-variate normal distributions in N dimensions Huang, Jingfang Fang, Fuhui Turkiyyah, George Cao, Jian Genton, Marc G. Keyes, David E. Numerical Analysis 03D20, 34B27, 62H10, 65C60, 65D30, 65T40 In this paper, we study the $N$-dimensional integral $ϕ(a,b; A) = \int_{a}^{b} H(x) f(x | A) \text{d} x$ representing the expectation of a function $H(X)$ where $f(x | A)$ is the truncated multi-variate normal (TMVN) distribution with zero mean, $x$ is the vector of integration variables for the $N$-dimensional random vector $X$, $A$ is the inverse of the covariance matrix $Σ$, and $a$ and $b$ are constant vectors. We present a new hierarchical algorithm which can evaluate $ϕ(a,b; A)$ using asymptotically optimal $O(N)$ operations when $A$ has "low-rank" blocks with "low-dimensional" features and $H(x)$ is "low-rank". We demonstrate the divide-and-conquer idea when $A$ is a symmetric positive definite tridiagonal matrix, and present the necessary building blocks and rigorous potential theory based algorithm analysis when $A$ is given by the exponential covariance model. Numerical results are presented to demonstrate the algorithm accuracy and efficiency for these two cases. We also briefly discuss how the algorithm can be generalized to a wider class of covariance models and its limitations. |
| title | O(N) Hierarchical algorithm for computing the expectations of truncated multi-variate normal distributions in N dimensions |
| topic | Numerical Analysis 03D20, 34B27, 62H10, 65C60, 65D30, 65T40 |
| url | https://arxiv.org/abs/1809.08315 |