Abstract
Given a determinate (multivariate) probability measure $\mu$, we characterize Gaussian mixtures $\nu_\phi$ which minimize the Wasserstein distance $W_2(\mu,\nu_\phi)$ to $\mu$ when the mixing probability measure $\phi$ on the parameters $(m,\Sigma)$ of the Gaussians is supported on a compact set $S$. (i) We first show that such mixtures are optimal solutions of a particular optimal transport (OT) problem where the marginal $\nu_\phi$ of the OT problem is also unknown via the mixing measure variable $\phi$. Next (ii) by using a well-known specific property of Gaussian measures, this optimal transport is then viewed as a Generalized Moment Problem (GMP) and if the set $S$ of mixture parameters $(m,\Sigma)$ is a basic compact semi-algebraic set, we provide a "mesh-free" numerical scheme to approximate as closely as desired the optimal distance by solving a hierarchy of semidefinite relaxations of increasing size. In particular, we neither assume that the mixing measure is finitely supported nor that the variance is the same for all components. If the original measure $\mu$ is not a Gaussian mixture with parameters $(m,\Sigma)\in S$, then a strictly positive distance is detected at a finite step of the hierarchy. If the original measure $\mu$ is a Gaussian mixture with parameters $(m,\Sigma)\in S$, then all semidefinite relaxations of the hierarchy have same zero optimal value. Moreover if the mixing measure is atomic with finite support, its components can sometimes be extracted from an optimal solution at some semidefinite relaxation of the hierarchy when Curto & Fialkow's flatness condition holds for some moment matrix.
Introduction
Gaussian Mixture Models (GMMs) are fundamental tools in statistics and machine learning, primarily used for density estimation and clustering. A central challenge in this domain is determining the "best" Gaussian mixture to represent an arbitrary probability distribution $\mu$. Traditional approaches often rely on heuristics like Expectation-Maximization (EM), which typically require a pre-specified number of components and often impose restrictive assumptions, such as uniform variance across components or fixed component counts.
In this work, Jean B. Lasserre proposes a rigorous mathematical framework to address these limitations. By framing the approximation problem through the lens of Optimal Transport (OT) and the Generalized Moment Problem (GMP), the author develops a "mesh-free" numerical scheme that converges to the optimal Gaussian mixture under the 2-Wasserstein distance.
Problem Formulation
The objective is to find a Gaussian mixture $\nu_\phi$ that minimizes the 2-Wasserstein distance $W_2(\mu, \nu_\phi)$ to a given determinate probability measure $\mu$. The mixture $\nu_\phi$ is defined by a mixing probability measure $\phi$ supported on a compact set $S$ of parameters $(m, \Sigma)$, where $m$ represents the mean and $\Sigma$ the covariance matrix.
Unlike standard OT problems where both the source and target measures are fixed, this formulation treats the target marginal $\nu_\phi$ as an unknown variable. The optimization is performed over the mixing measure $\phi$, allowing for a flexible representation that does not assume a fixed number of components or identical variances among them.
Methodology: From OT to GMP
The paper's methodology rests on two primary theoretical pillars:
1. Optimal Transport with Unknown Marginals
The author demonstrates that the minimization of $W_2(\mu, \nu_\phi)$ can be recast as a linear optimization problem over measures. By exploiting the structure of the Wasserstein distance, the problem becomes finding a coupling that minimizes transport cost while the target marginal is constrained to be a Gaussian mixture. This formulation allows the target distribution to be optimized simultaneously with the transport plan.
2. The Polynomial Property of Gaussian Moments
A critical observation in this work is that the $j$-th moment of a Gaussian distribution is an explicit polynomial of degree $j$ in its parameters $(m, \Sigma)$. This property allows the transformation of the measure-based optimization problem into a Generalized Moment Problem (GMP). If the parameter set $S$ is a basic compact semi-algebraic set, the problem becomes amenable to algebraic optimization techniques.
Numerical Scheme: The Moment-SOS Hierarchy
To solve the resulting GMP, the author employs the Moment-SOS (Sum-of-Squares) hierarchy, also known as the Lasserre hierarchy. This approach involves solving a sequence of increasingly large Semidefinite Programming (SDP) relaxations.
As the degree of the moments considered in the hierarchy increases, the sequence of optimal values converges to the true minimum Wasserstein distance. This method is "mesh-free," meaning it does not require the discretization of the underlying space (a common requirement in numerical OT), which is a significant advantage for high-precision applications.
Parameter Extraction
For cases where the optimal mixing measure $\phi$ is atomic (i.e., the mixture consists of a finite number of Gaussians), the parameters can often be recovered exactly. By applying Curto and Fialkow’s flatness condition to the moment matrix obtained from an optimal SDP solution, one can extract the means and variances of the constituent Gaussians using linear algebra subroutines.
Key Insights and Results
- Convergence and Existence: The paper proves that an optimal mixing measure always exists under compact constraints and that the SDP hierarchy provides a systematic way to reach it.
- Certificate of Non-Gaussianity: If the target measure $\mu$ cannot be represented as a Gaussian mixture within the parameter set $S$, the hierarchy will yield a strictly positive distance at a finite step, providing a mathematical certificate of the model's approximation error.
- Flexibility: The framework naturally handles multivariate distributions and does not require components to share the same covariance structure, overcoming a common limitation in simplified GMM research.
- Empirical Validation: Using synthetic examples (e.g., a univariate mixture of two Gaussians), the author demonstrated that the algorithm (via GloptiPoly) successfully detected the correct mixing measure and extracted parameters at the 6th step of the hierarchy.
Conclusion and Future Work
This research provides a powerful theoretical and numerical bridge between optimal transport and polynomial optimization. While the Moment-SOS hierarchy offers a robust path to global optimality, the computational cost of SDPs remains a challenge for very high-dimensional data, as the size of the programs grows rapidly with the dimension $d$ and relaxation degree $n$. Future research may focus on improving the scalability of these relaxations or exploring alternative distance metrics, such as Total Variation, within the same GMP framework.
Summary updated