Hierarchical-Block Conditioning Approximations for High-Dimensional Multivariate Normal Probabilities

• Activity Number: 253 - Contributed Poster Presentations: Section on Statistical Computing
• Type: Contributed
• Date/Time: Monday, July 30, 2018 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Jian Cao* and Marc G Genton and David E Keyes and George Turkiyyah
• Companies: King Abdullah University of Science and Technology and King Abdullah University of Science and Technology and King Abdullah University of Science and Technology and King Abdullah University of Science and Technology
• Keywords: Block reordering; d-dimensional conditioning; Hierarchical representation; Spatial covariance functions; Univariate reordering

Abstract

This paper presents a new method to estimate large-scale multivariate normal probabilities. The approach combines a hierarchical representation with processing of the covariance matrix that decomposes the n-dimensional problem into a sequence of smaller m-dimensional ones. It also includes a d-dimensional conditioning method that further decomposes the m-dimensional problems into smaller d-dimensional problems. The resulting two-level hierarchical-block conditioning method requires Monte Carlo simulations to be performed only in d dimensions, with d < < n, and allows the complexity of the algorithm's major cost to be O(nlog n). We also introduce an inexpensive block reordering strategy to provide improved accuracy in the overall probability computation. Numerical simulations on problems from 2D spatial statistics with dimensions up to 16384 indicate that the algorithm achieves a 1% error level and improves the run time over a one-level hierarchical Quasi-Monte Carlo method by a factor between 10 and 15.