Hierarchical-block conditioning approximations for high-dimensional multivariate normal probabilities

Jian Cao*, Marc G. Genton, David E. Keyes, George M. Turkiyyah

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


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). The run-time cost of the method depends on two parameters, m and d, where m represents the diagonal block size and controls the sizes of the blocks of the covariance matrix that are replaced by low-rank approximations, and d allows a trade-off of accuracy for expensive computations in the evaluation of the probabilities of m-dimensional blocks. We also introduce an inexpensive block reordering strategy to provide improved accuracy in the overall probability computation. The downside of this method, as with other such conditioning approximations, is the absence of an internal estimate of its error to use in tuning the approximation. Numerical simulations on problems from 2D spatial statistics with dimensions up to 16,384 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.

Original languageEnglish (US)
Pages (from-to)585-598
Number of pages14
Issue number3
StatePublished - May 1 2019


  • Block reordering
  • Hierarchical representation
  • Spatial covariance functions
  • Univariate reordering
  • d-Dimensional conditioning

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Computational Theory and Mathematics


Dive into the research topics of 'Hierarchical-block conditioning approximations for high-dimensional multivariate normal probabilities'. Together they form a unique fingerprint.

Cite this