Abstract
This paper investigates the use of multilevel Monte Carlo (MLMC) methods for estimating the expectation of discretized random fields. In scenarios where numerical simulators have inconsistent dimensions across the multilevel hierarchy, grid transfer operators—prolongation and restriction—are required. However, these operators can introduce high-frequency noise and aliasing, which inflates estimator variance. We propose a Filtered MLMC (F-MLMC) estimator that incorporates smoothing operators to dampen these spurious features. Through a theoretical spectral analysis and numerical experiments involving 1D diffusion and 2D diffusion-based covariance operators, we demonstrate that F-MLMC significantly reduces variance compared to both crude Monte Carlo and standard MLMC, while remaining unbiased.
Introduction
Monte Carlo (MC) methods are essential for estimating expectations in complex systems, but their slow convergence rate often makes them computationally prohibitive. Multilevel Monte Carlo (MLMC) addresses this by utilizing a hierarchy of discretization levels. By performing many inexpensive simulations on coarse grids and a few expensive simulations on fine grids, MLMC constructs a telescoping sum that reduces the overall computational cost required to achieve a target mean square error.
While MLMC is well-established for scalar outputs, its application to discretized random fields—such as spatial maps of physical properties—introduces unique challenges. Estimating a random field requires comparing outputs across different grid resolutions. This necessitates grid transfer operators borrowed from multigrid methods. However, the interpolation and averaging inherent in these transfers can introduce spectral inconsistencies, leading to "noise" that can diminish or even negate the efficiency gains of the multilevel approach.
The Problem: Grid Transfer and Aliasing
In a standard MLMC setup, the estimator relies on the correlation between a fine-level simulation and a coarse-level simulation. To compute the difference between these levels, the coarse-grid output must be mapped to the fine grid (prolongation) or vice versa (restriction).
This paper identifies a critical "spectral" problem: grid transfer operators are imperfect signal processors. Specifically, they introduce aliasing, where high-frequency components on a fine grid are misinterpreted as low-frequency signals on a coarse grid. This mismatch creates artificial variance in the telescoping sum. In some complex spatial applications, this noise is so significant that standard MLMC performs worse than a simple, single-level crude Monte Carlo estimator.
Methodology: Filtered MLMC (F-MLMC)
To mitigate the noise introduced by grid transfers, we introduce the Filtered MLMC (F-MLMC) estimator. This method incorporates a smoothing mechanism inspired by the relaxation steps in multigrid solvers. The approach consists of two primary filtering stages:
- Pre-filtering: Before a fine-grid signal is restricted to a coarse grid, a low-pass filter is applied to remove high-frequency scales that the coarse grid cannot accurately represent.
- Post-filtering: After a coarse-grid signal is prolongated to the fine grid, a second filter is applied to smooth out artifacts created by the interpolation process.
For these filters, we utilize second-order Shapiro filters, which are computationally efficient and effective at damping high-frequency noise without significantly altering the underlying low-frequency signal.
Spectral Analysis
To provide a theoretical foundation for F-MLMC, we perform a spectral analysis using the Hartley basis (a real-valued alternative to the Fourier transform). This analysis allows us to quantify how variance is distributed across different spatial frequencies. We demonstrate mathematically that the filtering operators specifically target and suppress the "spurious" high-frequency components that drive variance inflation in the MLMC telescoping sum.
Experimental Results
The F-MLMC method was evaluated against two benchmarks to verify the theoretical findings:
1D Diffusion Illustration
A synthetic one-dimensional diffusion problem on a periodic domain was used to verify the spectral theory. In this controlled environment, F-MLMC achieved a 90% reduction in total variance compared to crude Monte Carlo and a 55% reduction compared to the best-performing unfiltered MLMC configuration.
2D Diffusion-Based Covariance
We applied the method to a non-linear problem: estimating the variance field of a diffusion-based covariance operator. This is a common task in ocean data assimilation, where researchers must estimate the "intrinsic variance" of a model to normalize correlation matrices. In cases with small-scale features, the standard MLMC estimator failed to outperform crude Monte Carlo due to excessive grid transfer noise. F-MLMC successfully suppressed this noise, reducing the variance below the crude MC baseline and proving robust even in non-linear settings.
Discussion and Conclusion
The primary insight of this work is that the MLMC hierarchy should be treated as a signal processing chain. By ensuring spectral consistency between levels, F-MLMC restores the efficiency of the multilevel approach for spatial data. Importantly, because the filtering is applied consistently within the telescoping sum, the F-MLMC estimator remains unbiased, converging to the same true value as a high-resolution fine-grid simulation.
Future work will explore the selection of "optimal" filters tailored to specific differential operators and the potential integration of F-MLMC with Quasi-Monte Carlo (QMC) methods to further accelerate convergence. Additionally, while our experiments did not yield negative values, further investigation into ensuring the non-negativity of estimated variance fields remains an open area for refinement.
Summary updated