Localization for MCMC: sampling high-dimensional posterior distributions\n with local structure

Matthias Morzfeld, Xin T. Tong, Youssef Marzouk

Abstract

We investigate how ideas from covariance localization in numerical weather prediction can be used in Markov chain Monte Carlo (MCMC) sampling of high-dimensional posterior distributions arising in Bayesian inverse problems. To localize an inverse problem is to enforce an anticipated "local" structure by (i) neglecting small off-diagonal elements of the prior precision and covariance matrices; and (ii) restricting the influence of observations to their neighborhood. For linear problems we can specify the conditions under which posterior moments of the localized problem are close to those of the original problem. We explain physical interpretations of our assumptions about local structure and discuss the notion of high dimensionality in local problems, which is different from the usual notion of high dimensionality in function space MCMC. The Gibbs sampler is a natural choice of MCMC algorithm for localized inverse problems and we demonstrate that its convergence rate is independent of dimension for localized linear problems. Nonlinear problems can also be tackled efficiently by localization and, as a simple illustration of these ideas, we present a localized Metropolis-within-Gibbs sampler. Several linear and nonlinear numerical examples illustrate localization in the context of MCMC samplers for inverse problems.

Introduction

Sampling from high-dimensional posterior distributions is a notorious bottleneck in Bayesian inference. Standard Markov chain Monte Carlo (MCMC) algorithms like Random Walk Metropolis (RWM), MALA, or Hamiltonian Monte Carlo (HMC) suffer from the "curse of dimensionality": as the number of variables ($n$) increases, the step size must decrease to maintain acceptance rates, causing the computational effort to skyrocket.

This research adapts "localization" techniques from numerical weather prediction to make MCMC sampling feasible for high-dimensional Bayesian inverse problems. By exploiting local structure—where variables and observations only interact within a neighborhood—we demonstrate that Gibbs samplers can achieve convergence rates that are independent of the total number of dimensions.

Methodology

The core idea is localization, which involves two main steps:

  1. Prior Localization: Neglecting small, far-away correlations in the prior. This means enforcing a "banded" structure on the prior covariance or precision matrices, setting off-diagonal elements to zero beyond a certain distance.
  2. Likelihood Localization: Restricting the influence of an observation to its immediate spatial neighborhood.
Figure 2: Illustration of a banded matrix structure where off-diagonal elements are neglected to enforce local structure.

The Gibbs sampler is the ideal tool for these localized problems. Because Gibbs updates variables in blocks, it naturally exploits the fact that a variable's conditional distribution only depends on its "neighbors." For nonlinear problems, we introduce a Localized Metropolis-within-Gibbs (l-MwG) sampler. This algorithm proposes a local move based on the prior and accepts or rejects it using only the "local" observations assigned to that specific block, significantly reducing the computational cost per step.

Key Insights

  • The "Local" Spectral Gap: We prove mathematically that for localized linear-Gaussian problems, the "spectral gap" (a measure of how fast the MCMC chain forgets its starting point) does not shrink as the domain grows. This guarantees dimension-independent performance.
  • Bandedness is Key: High-dimensional matrices are easy to handle if they are sparse (banded). If the prior and the observation matrix are both local, the posterior inherits this bandedness, making it much easier to sample.
  • Redefining High-D: We distinguish between "function space" high-dimensionality (refining a grid) and "local structure" high-dimensionality (adding more grid points to a larger area). While samplers like pCN excel at the former, localized Gibbs samplers are required for the latter.

Experimental Results

We validated our approach using several synthetic benchmarks, including 1D Linear-Gaussian models, 2D Image Deblurring ($256 \times 256$ image), and the Lorenz ’96 model ($n=40$ and $n=400$).

Figure 1: Comparison of Integrated Auto-Correlation Time (IACT) vs. Dimension for standard MCMC samplers, showing the rapid increase in computational effort as dimensionality grows.
  • Constant Efficiency: In linear tests, the Integrated Auto-Correlation Time (IACT) remained flat as the dimension $n$ increased for localized Gibbs. In contrast, IACT for RWM and HMC grew linearly or by square roots, as shown in the scaling plots above.
  • Image Deblurring Success: For the $256 \times 256$ image, the localized Gibbs sampler achieved an IACT near 1.0 (nearly perfect efficiency), while standard MALA and pCN failed to produce usable results because they couldn't handle the high effective dimension.
  • Nonlinear Performance: In the Lorenz '96 example, the localized MwG sampler outperformed MALA and pCN by orders of magnitude. At $n=400$, l-MwG had an IACT of ~43-257, while MALA and pCN were over 3,000.

Limitations and Future Work

Localization is not a universal solution. It is less effective for problems with global dependencies, such as computed tomography (CT) scans, where every observation passes through the entire domain. Additionally, much of the current theory relies on Gaussian priors; extending this to highly non-Gaussian "local" fields remains a challenge. Future work will also address the "low-noise limit," where simple l-MwG samplers can struggle as the posterior becomes significantly narrower than the prior.

Summary updated

Abstract

We investigate how ideas from covariance localization in numerical weather\nprediction can be used in Markov chain Monte Carlo (MCMC) sampling of\nhigh-dimensional posterior distributions arising in Bayesian inverse problems.\nTo localize an inverse problem is to enforce an anticipated "local" structure\nby (i) neglecting small off-diagonal elements of the prior precision and\ncovariance matrices; and (ii) restricting the influence of observations to\ntheir neighborhood. For linear problems we can specify the conditions under\nwhich posterior moments of the localized problem are close to those of the\noriginal problem. We explain physical interpretations of our assumptions about\nlocal structure and discuss the notion of high dimensionality in local\nproblems, which is different from the usual notion of high dimensionality in\nfunction space MCMC. The Gibbs sampler is a natural choice of MCMC algorithm\nfor localized inverse problems and we demonstrate that its convergence rate is\nindependent of dimension for localized linear problems. Nonlinear problems can\nalso be tackled efficiently by localization and, as a simple illustration of\nthese ideas, we present a localized Metropolis-within-Gibbs sampler. Several\nlinear and nonlinear numerical examples illustrate localization in the context\nof MCMC samplers for inverse problems.\n
BibTeX
@article{morzfeld2019localization,
  author = {Matthias Morzfeld and Xin T. Tong and Youssef Marzouk},
  title = {{Localization for MCMC: sampling high-dimensional posterior distributions\textbackslash\{\}n with local structure}},
  journal = {Journal of Computational Physics},
  year = {2019},
  doi = {10.1016/j.jcp.2018.12.008},
}
Figure