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:
- 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.
- Likelihood Localization: Restricting the influence of an observation to its immediate spatial neighborhood.
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$).
- 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