An O(N) algorithm for computing expectation of N-dimensional truncated multi-variate normal distribution II: computing moments and sparse grid acceleration
An O(N) algorithm for computing expectation of N-dimensional truncated multi-variate normal distribution II: computing moments and sparse grid acceleration
复制标题
计算N维截断多元正态分布期望的O(N)算法II：计算矩和稀疏网格加速度
DOI：
10.1007/s10444-022-09988-6
复制
发表时间：
2022
影响因子：
1.7
通讯作者：
Wu, Yichao
中科院分区：
文献类型：
--
作者：
Zheng, Chaowen;Tang, Zhuochao;Huang, Jingfang;Wu, Yichao
在先前的论文（Huang等人，Advances in Computational Mathematics 47（5）：1-34，2021）中，我们提出了一种新的分层算法的基本原理，用于计算满足截断多变量正态（TMVN）分布的N维函数的期望。该算法假设协方差矩阵和精度矩阵为低秩块，具有低维特征.给出了当A为三对角和指数模型时的分析和数值结果。在本文中，我们首先演示了分层算法结构如何允许同时计算所有阶M和更少阶矩E（H（X）= X1 m1 <$XNmN| ai<Xi<bi，i= 1，.，N），当时使用渐近最优运算，当时使用渐近最优运算.在期望最大化（EM）算法中经常需要这些矩。我们说明了算法的想法，使用的情况下，当A是三对角或指数模型的非对角矩阵块的秩和有效变量的数量与层次树节点相关联的每个功能。较小的KandP值允许使用现有的FFT和非均匀FFT（NuFFT）求解器来加速系统中压缩特征的计算。为了处理具有较高KandP值的情况，我们引入了针对问题的稀疏网格技术。我们提出了计算的时刻和higherKandP值的数值结果来证明算法的精度和效率。最后，我们总结了我们的结果并讨论了局限性和概括性，特别是我们的算法能力受到更高维度数学工具可用性的限制。当大于20时，据我们所知，没有实用的工具可以解决20个真正独立变量的问题。
In a previous paper (Huang et al.,Advances in Computational Mathematics47(5):1–34, 2021), we presented the fundamentals of a new hierarchical algorithm for computing the expectation of aN-dimensional functionwheresatisfies the truncated multi-variate normal (TMVN) distribution. The algorithm assumes thatis low-rank and the covariance matrixand precision matrixhave low-rank blocks with low-dimensional features. Analysis and numerical results were presented whenAis tridiagonal or given by the exponential model. In this paper, we first demonstrate how the hierarchical algorithm structure allows the simultaneous calculations of all the orderMand less moments E(H(X)=X1m1⋯XNmN|ai<Xi<bi,i=1,…,N),using asymptotically optimaloperations whenandoperations when. Thesemoments are often required in the Expectation Maximization (EM) algorithms. We illustrate the algorithm ideas using the case whenAis tridiagonal or the exponential model where the off-diagonal matrix block has rankand number of effective variablesfor each function associated with a hierarchical tree node. The smallerKandPvalues allow the use of existing FFT and Non-uniform FFT (NuFFT) solvers to accelerate the computation of the compressed features in the system. To handle cases with higherKandPvalues, we introduce the sparse grid technique aimed at problems with. We present numerical results for computing both the moments and higherKandPvalues to demonstrate the accuracy and efficiency of the algorithms. Finally, we summarize our results and discuss the limitations and generalizations, in particular, our algorithm capability is limited by the availability of mathematical tools in higher dimensions. Whenis greater than 20, as far as we know, there are no practical tools available for problems with 20 truly independent variables.
稀疏网格 Matlab 套件 - 用于高维函数逼近和不确定性量化的稀疏网格的 Matlab 实现
DOI：
10.48550/arxiv.2203.09314
发表时间：
2022
期刊：
ArXiv
影响因子：
--
作者：
C. Piazzola;L. Tamellini
通讯作者：
L. Tamellini
计算 N 维截断多元正态分布期望的 O(N) 算法 I：基础知识
影响因子：
1.7
作者：
Huang, Jingfang;Cao, Jian;Fang, Fuhui;Genton, Marc G.;Keyes, David E.;Turkiyyah, George
通讯作者：
Turkiyyah, George