Hierarchical Decompositions for the Computation of High-Dimensional Multivariate Normal Probabilities

We present a hierarchical decomposition scheme for computing the <i>n</i>-dimensional integral of multivariate normal probabilities that appear frequently in statistics. The scheme exploits the fact that the formally dense covariance matrix can be approximated by a matrix with a hierarchical low-rank structure. It allows the reduction of the computational complexity per Monte Carlo sample from O(n2) to O(mn+knlog(n/m)), where <i>k</i> is the numerical rank of off-diagonal matrix blocks and <i>m</i> is the size of small diagonal blocks in the matrix that are not well-approximated by low-rank factorizations and treated as dense submatrices. This hierarchical decomposition leads to substantial efficiencies in multivariate normal probability computations and allows integrations in thousands of dimensions to be practical on modern workstations. Supplementary material for this article is available online.

本文提出一种用于计算统计学中频繁出现的多元正态概率的n维积分的分层分解方案。该方案利用了形式上为稠密的协方差矩阵（covariance matrix）可被近似为具有分层低秩结构的矩阵这一特性，可将单个蒙特卡洛样本（Monte Carlo sample）的计算复杂度从O(n²)降低至O(mn + knlog(n/m))，其中k为矩阵非对角块的数值秩，m为矩阵中无法通过低秩分解（low-rank factorizations）实现良好近似、需作为稠密子矩阵（dense submatrices）处理的小型对角块的尺寸。该分层分解可显著提升多元正态概率计算的效率，使得数千维空间内的积分运算在现代工作站上即可实现实用化。本文的补充材料可在线获取。