High-dimensional Gaussian sampling: a review and a unifying approach based on a stochastic proximal point algorithm

Abstract

Efficient sampling from a high-dimensional Gaussian distribution is an old but high-stake issue. Vanilla Cholesky samplers imply a computational cost and memory requirements which can rapidly become prohibitive in high dimension. To tackle these issues, multiple methods have been proposed from different communities ranging from iterative numerical linear algebra to Markov chain Monte Carlo (MCMC) approaches. Surprisingly, no complete review and comparison of these methods have been conducted. This paper aims at reviewing all these approaches by pointing out their differences, close relations, benefits and limitations. In addition to this state of the art, this paper proposes a unifying Gaussian simulation framework by deriving a stochastic counterpart of the celebrated proximal point algorithm in optimization. This framework offers a novel and unifying revisit of most of the existing MCMC approaches while extending them. Guidelines to choose the appropriate Gaussian simulation method for a given sampling problem in high dimension are proposed and illustrated with numerical examples.

arXiv comment53 pages, 11 figures

References in corpus (8)

• Fast Image Recovery Using Variable Splitting and Constrained Optimization
• An Augmented Lagrangian Approach to the Constrained Optimization Formulation of Imaging Inverse Problems
• Bayesian estimation of regularization and PSF parameters for Wiener-Hunt deconvolution
• Split-and-augmented Gibbs sampler - Application to large-scale inference problems
• Efficient Gaussian Sampling for Solving Large-Scale Inverse Problems using MCMC Methods
• Asymptotically exact data augmentation: models, properties and algorithms
• Gradient Scan Gibbs Sampler: an efficient algorithm for high-dimensional Gaussian distributions
• Efficient simulation of Gaussian Markov random fields by Chebyshev polynomial approximation

Cited by in corpus (6)

• Efficient MCMC Sampling with Dimension-Free Convergence Rate using ADMM-type Splitting
• Personalised Federated Learning On Heterogeneous Feature Spaces
• Batched Bayesian optimization by maximizing the probability of including the optimum
• Leveraging joint sparsity in hierarchical Bayesian learning
• Data augmentation for the POD formulation of the parametric laminar incompressible Navier-Stokes equations
• A Statistical Framework to Investigate the Optimality of Signal-Reconstruction Methods