An O(N) algorithm for computing expectation of N-dimensional truncated multi-variate normal distribution I: fundamentals
An O(N) algorithm for computing expectation of N-dimensional truncated multi-variate normal distribution I: fundamentals
复制标题
计算 N 维截断多元正态分布期望的 O(N) 算法 I：基础知识
DOI：
10.1007/s10444-021-09888-1
复制
发表时间：
2021
影响因子：
1.7
通讯作者：
Turkiyyah, George
中科院分区：
文献类型：
--
作者：
Huang, Jingfang;Cao, Jian;Fang, Fuhui;Genton, Marc G.;Keyes, David E.;Turkiyyah, George
本文给出了计算函数H（X）期望的N维积分的分层算法的基本原理，其中f（x| A）是具有零均值的截断多变量正态（TMVN）分布，x是N维随机向量X的积分变量向量，A是协方差矩阵的逆，a和裸常数向量。该算法假设H（x）是“低秩”的，并且被设计为适当地聚类X，使得矩阵A具有“低秩”块和“低维”特征。我们证明了分而治之的想法时，A是一个对称正定三对角矩阵，并提出了必要的积木和严格的潜在的理论为基础的算法分析时，A是由指数协方差模型。对于N维问题，该算法的总复杂度为O（N），前因子由非对角矩阵块的秩和有效变量的个数决定。用快速傅里叶变换和非均匀傅里叶变换在16G的台式计算机上得到了高达2048的高精度结果，验证了分析的正确性。目前的文件集中的想法，使用简单而有代表性的例子，其中非对角矩阵块的秩为1，有效变量的数量是由2界定，允许简洁的符号和更容易解释。在随后的文章中，我们讨论了推广目前的计划，使用稀疏网格技术的高秩问题，并证明如何所有的时刻k阶或更少（总O（Nk）积分）可以计算使用O（Nk）操作fork≥ 2和操作fork= 1。
In this paper, we present the fundamentals of a hierarchical algorithm for computing theN-dimensional integralrepresenting the expectation of a functionH(X) wheref(x|A) is the truncated multi-variate normal (TMVN) distribution with zero mean,xis the vector of integration variables for theN-dimensional random vectorX,Ais the inverse of the covariance matrixΣ, andaandbare constant vectors. The algorithm assumes thatH(x) is “low-rank” and is designed for properly clusteredXso that the matrixAhas “low-rank” blocks and “low-dimensional” features. We demonstrate the divide-and-conquer idea whenAis a symmetric positive definite tridiagonal matrix and present the necessary building blocks and rigorous potential theory–based algorithm analysis whenAis given by theexponential covariance model. The algorithm overall complexity isO(N) forN-dimensional problems, with a prefactor determined by the rank of the off-diagonal matrix blocks and number of effective variables. Very high accuracy results forNas large as 2048 are obtained on a desktop computer with 16G memory using the fast Fourier transform (FFT) and non-uniform FFT to validate the analysis. The current paper focuses on the ideas using the simple yet representative examples where the off-diagonal matrix blocks are rank 1 and the number of effective variables is bounded by 2, to allow concise notations and easier explanation. In a subsequent paper, we discuss the generalization of current scheme using the sparse grid technique for higher rank problems and demonstrate how all the moments ofkthorder or less (a total ofO(Nk) integrals) can be computed usingO(Nk) operations fork≥ 2 andoperations fork= 1.
登录
查看更多内容
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
Yamamoto;et al.
通讯作者：
et al.
DOI：
10.1111/rssb.12162
发表时间：
2017-01-01
影响因子：
5.8
作者：
Botev, Z. I.
通讯作者：
Botev, Z. I.
影响因子：
1.8
作者：
Ioannis Phinikettos;A. Gandy
通讯作者：
A. Gandy
中性介子混合中的衰减时间积分及其高效评估
DOI：
--
发表时间：
2014
期刊：
影响因子：
--
作者：
T. M. Karbach;G. Raven;M. Schiller
通讯作者：
M. Schiller
DOI：
10.1017/cbo9781139248891
发表时间：
2018-03
期刊：
--
影响因子：
--
作者：
A. Azzalini;A. Capitanio
通讯作者：
A. Azzalini;A. Capitanio