Collaborative Research: A Fast Hierarchical Algorithm for Computing High Dimensional Truncated Multivariate Gaussian Probabilities and Expectations

维度灾难严重限制了人类在许多应用领域处理高维数据的能力。然而，现有的人类知识数据库中的大多数有用数据都具有一定的可压缩特性。本项目致力于这些可压缩特征的数学描述，并开发了一种新的分层建模技术来从科学和工程应用中的高维数据集中提取这些特征，并在分层树结构上高效地处理压缩信息。研究人员将为高维积分开发快速算法，涉及截断的多变量正态分布，目标是分析医学数据集。该项目开发的技术将为科学界提供一个处理高维数据集的非常强大的工具，同时促进对具有跨学科知识的研究人员的培训。多元高斯分布是统计学中最重要的连续分布之一。如果某些分量被限制在有限或半有限的区间内，则称为截断多元正态分布(TMVN)。许多统计算法依赖于对TMVN的概率和期望的评估，特别是在期望最大化(EM)类型的算法中。直接计算期望是非常具有挑战性的。一种常用的替代方法是基于蒙特卡罗模拟，从相应的TMVN分布中抽取随机样本。然而，在高维情况下从TMVN分布模拟同样具有挑战性。该项目将开发新的分层算法，以有效地计算非常高维的TMVN概率和期望。其核心思想包括层次数据聚类、低等级和低维特征提取及其在层次树结构上的高效处理。该算法可以在高维情况下计算一类p维TMVN分布在渐近最优O(P)运算下的期望值，并可用于在接受-拒绝方法中收紧目标TMVN分布的似然比上界，以获得最高的接受概率，同时避免了一些竞争算法(如Metropolis-Hastings算法)的老化周期。该算法的分层性质允许轻松采用自适应、动态和异步运行时系统中的最新进展，以有效地在规模上利用计算资源。该项目提供了先进的数值工具，以加速计算并提高EM算法处理大型和复杂生物医学数据的适用性，目标应用旨在改善公众健康。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The "curse of dimensionality" has severely limited human's capability of handling high-dimensional data in many application domains. However, most useful data in existing human knowledge database has certain compressible features. This project focuses on the mathematical description of these compressible features, and develops a novel hierarchical modeling technique to extract these features from high-dimensional datasets in science and engineering applications and process the compressed information efficiently on a hierarchical tree structure. The investigators will develop fast algorithms for high-dimensional integrations involving a truncated multivariate normal distribution that targets the analysis of medical datasets. The techniques developed from this project will provide the scientific community a very powerful tool to handle high-dimensional datasets and at the same time foster the training of researchers with interdisciplinary knowledge. Multivariate Gaussian distribution is one of the most important continuous distributions in statistics. If some components are restricted to an interval, either finite or semi-finite, it is referred to as the truncated multivariate normal (TMVN) distribution. Many statistical algorithms rely on the evaluations of the probabilities and expectations with respect to a TMVN, especially in the expectation-maximization (EM) type algorithms. Direct computation of the desired expectation is very challenging. A commonly used alternative approach is based on the Monte Carlo simulation by drawing random samples from the corresponding TMVN distribution. However, it is equally challenging to simulate from a TMVN distribution in high dimensional cases. This project will develop new hierarchical algorithms to efficiently compute very high dimensional TMVN probabilities and expectations. The core ideas include the hierarchical data clustering, low-rank and low-dimensional features extraction, and their efficient processing on the hierarchical tree structures. The resulting algorithm can compute the expectations with respect to a class of p-dimensional TMVN distributions in asymptotically optimal O(p) operations in high dimensional cases, which can also be used to tighten the likelihood ratio bound of the target TMVN distribution in the acceptance-rejection method to achieve the highest acceptance probability while avoiding the burn-in period of some competitive algorithms such as the Metropolis-Hastings algorithm. The hierarchical nature of the algorithm allows easy adoption of the recent progress in adaptive, dynamic, and asynchronous runtime systems to efficiently utilize the computing resources at scale. The project provides advanced numerical tools to accelerate the computations and improve the applicability of the EM algorithms to handle large and complex biomedical data, with target applications aimed at improving public health.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.