Abstract
We provide a numerical scheme to approximate as closely as desired the Gaussian or exponential measure $\mu(\Omega)$ of (not necessarily compact) basic semi-algebraic sets $\Omega \subset \mathbb{R}^n$. We obtain two monotone (non-increasing and non-decreasing) sequences of upper and lower bounds $(\overline{\omega}_d)$ and $(\underline{\omega}_d)$, $d \in \mathbb{N}$, each converging to $\mu(\Omega)$ as $d \to \infty$. For each $d$, computing $\overline{\omega}_d$ or $\underline{\omega}_d$ reduces to solving a semidefinite program (SDP) whose size increases with $d$. Some preliminary (small dimension) computational experiments are encouraging and illustrate the potential of the method. The method also works for any measure whose moments are known and which satisfies Carleman's condition.
Introduction
In statistics, probability, and geometry, a fundamental challenge is calculating the "weight" or measure of a complex shape under a specific probability distribution. While calculating the Gaussian measure of a simple box or ball is straightforward, the problem becomes significantly more difficult when the region is a basic semi-algebraic set—a shape defined by a collection of polynomial inequalities $g_j(x) \geq 0$.
Existing numerical integration techniques often struggle with regions that are non-compact (unbounded), such as half-spaces or the areas outside of curves. This paper, authored by Jean B. Lasserre, introduces a systematic numerical framework to compute these measures with theoretical guarantees of convergence for both bounded and unbounded regions.
The Moment-SOS Framework
The proposed method leverages the Generalized Problem of Moments (GPM) and the Moment-SOS (Sum of Squares) hierarchy. The approach is built on several key pillars:
- Moment Matching: If the moments of a measure (mean, variance, skewness, etc.) are known, the measure can be uniquely identified, provided it satisfies Carleman’s condition. Since the moments of Gaussian and exponential distributions are known in closed form, they serve as the foundation for the constraints.
- SDP Relaxations: The problem of finding the measure of a set is reformulated as a linear program over a space of measures. This infinite-dimensional problem is "relaxed" into a sequence of finite-dimensional Semidefinite Programs (SDPs) of increasing size $d$.
- Dual Bounds: A significant advantage of this method is that it produces two monotone sequences: an upper bound $(\overline{\omega}_d)$ and a lower bound $(\underline{\omega}_d)$. These bounds strictly "sandwich" the true value, providing a built-in certificate of the approximation error.
Accelerating Convergence with Stokes' Theorem
A primary challenge in moment-based methods is the "Gibbs effect," where oscillations occur near the boundaries of the set, slowing down convergence. To mitigate this, Lasserre introduces a novel constraint based on Stokes’ Theorem. By relating the moments of the measure over the set to the moments over its boundary, the author creates a powerful regularizer. This inclusion forces the moments to behave correctly relative to the set's geometry, drastically improving the numerical scheme's speed and accuracy.
Experimental Results
The method was evaluated on several synthetic 2D geometric benchmarks, including:
- Compact sets: Non-centered Euclidean balls and ellipsoids.
- Non-compact sets: Half-spaces, hyperbolas, and non-convex quadratic regions.
- Simplexes: Used to validate numerical results against exact values derived via Laplace transform techniques.
In low-dimensional tests, the method demonstrated high precision. For example, in a test involving a non-centered ball, the error was reduced to 0.002% at relaxation order $d=9$. The experiments confirmed that the upper and lower bounds converge reliably toward the exact measure as the relaxation order increases.
Discussion and Limitations
While the framework is theoretically robust and works for any measure satisfying Carleman's condition, it faces practical hurdles:
- The Curse of Dimensionality: The size of the SDP grows combinatorially with the number of variables $n$ and the degree $d$. While highly effective for 2D and 3D problems, scaling to high-dimensional spaces remains computationally intensive.
- Numerical Conditioning: The current implementation uses the standard monomial basis ($1, x, x^2, \dots$), which can lead to ill-conditioned matrices as the degree increases.
Future work suggests that transitioning from monomials to orthogonal polynomials (such as Hermite polynomials for Gaussian measures) could significantly improve numerical stability and allow for higher-order approximations in more complex scenarios.
Summary updated