A Wasserstein-type distance in the space of Gaussian Mixture Models

Julie Delon; Agnes Desolneux

Source-linked AI summary

A Wasserstein-type distance in the space of Gaussian Mixture Models

Julie Delon, Agnes Desolneux

arXiv:1907.05254v4Jul 11, 2019math.OC

TL;DR

Optimal transport remains computationally intractable in high dimensions. The paper restricts couplings to Gaussian mixture models, yielding a finite discrete formulation whose complexity depends on component counts rather than space dimension, and studies related barycenters and applications.

Problem
Optimal transport’s numerical complexity has limited its use with large datasets, while Wasserstein computation remains intractable in sufficiently high dimensions.
Method
The paper restricts optimal-transport couplings to Gaussian mixture models and derives a finite discrete formulation, extending the framework to multi-marginal, barycenter, and generalized mixture settings.
Results
The resulting MW2 distance is geodesic, exceeds W2, is bounded by W2 plus a covariance-trace term, and supports color-transfer and texture-synthesis applications.
Takeaways & Limitations
Restricting couplings to Gaussian mixtures provides a dimension-independent discrete optimization framework for studying transport distances and image-processing tasks.
Takeaways & Limitations
Extending the methodology beyond Gaussian mixtures requires mixture families to be identifiable and closed under marginalization.

Abstract

from arXiv · show

In this paper we introduce a Wasserstein-type distance on the set of Gaussian mixture models. This distance is defined by restricting the set of possible coupling measures in the optimal transport problem to Gaussian mixture models. We derive a very simple discrete formulation for this distance, which makes it suitable for high dimensional problems. We also study the corresponding multi-marginal and barycenter formulations. We show some properties of this Wasserstein-type distance, and we illustrate its practical use with some examples in image processing.

1. Introduction.

The paper introduces MW2, a Wasserstein-type distance for Gaussian mixture models (GMM) that restricts couplings to GMMs, yielding a finite-dimensional discrete formulation. It develops multi-marginal, barycenter, and generalized formulations, and demonstrates applications in image processing.

Motivation: High-dimensional optimal transport remains computationally intractable despite efficient numerical approaches expanding its applications.This motivates a computationally simpler distance construction for GMMs.
MW2 construction: Restricting couplings to Gaussian mixture models converts the infinitely dimensional optimization problem into a finite-dimensional problem depending only on mixture Gaussian parameters.The restriction preserves the modeling class because general optimal transport plans and geodesics between GMMs are not usually GMMs.
MW2 construction: For the ground cost c(x, y) = ∥x−y∥2, the resulting geodesic distance is called MW2 and is larger than the classical W2 distance.MW2 denotes Mixture Wasserstein.
Contributions: The paper derives an explicit optimal-transport formula for GMM-restricted couplings and studies how the resulting distance compares with the classical Wasserstein distance.It also analyzes the multi-marginal and barycenter formulations and their relationship.
Contributions: The authors propose a generalized formulation for non-GMM distributions and apply MW2 to image processing.Python code is made available for reproducibility, and the paper reports two image-processing applications.

2. Reminders: Wasserstein distances and barycenters between probability measures on Rd.

This section recalls Wasserstein distances, optimal transport plans, displacement interpolation, and barycenters, including their multi-marginal formulation. It also summarizes explicit Gaussian results and motivates restricting transport plans to Gaussian mixture models.

Wasserstein distances: The p-Wasserstein distance is defined by minimizing the expected pth-power Euclidean transport cost over all couplings with prescribed marginals.An optimal coupling exists, and its distribution is an optimal transport plan.
Displacement interpolation and barycenters: For p = 2, an optimal transport plan generates a constant-speed geodesic called displacement interpolation, characterized as a Wasserstein barycenter between two measures.The interpolation minimizes the weighted sum of squared W2 distances to the endpoints.
Multi-marginal barycenters: For J probability distributions, a Wasserstein barycenter minimizes the weighted sum of squared W2 distances, and if one input has a density, the barycenter is unique.Barycenter solutions are related to multi-marginal transport solutions, with equal infima under the stated pushforward relation.
Gaussian measures: For Gaussian measures, W2 admits a closed-form expression; when covariances are non-degenerate, the geodesic remains Gaussian with linearly interpolated means and an explicitly interpolated covariance structure.With a nonsingular initial covariance, the optimal map is affine; the covariance interpolation also extends to singular matrices using the Moore-Penrose pseudoinverse.
Motivation for Gaussian mixture models: The paper investigates the optimal transport problem for finite Gaussian mixture models when the transport plan is constrained to remain a Gaussian mixture model.This motivates the subsequent study of mixture-model properties needed for the construction.

3. Some properties of Gaussian Mixtures Models.

This section establishes approximation and identifiability properties of finite Gaussian mixtures, then shows that ordinary optimal transport plans and barycenters between mixtures are generally not Gaussian mixtures. These observations motivate restricting admissible transport plans to Gaussian mixtures to obtain a well-defined Wasserstein-type distance with a discrete formulation.

Approximation: Finite Gaussian mixture distributions are dense in Pp(Rd) under Wp for every p ≥1.Dirac masses are degenerate Gaussian distributions, so approximation by finite convex combinations of Dirac masses yields the result.
Identifiability: Compact finite Gaussian mixtures are identifiable up to reordering: equality requires matching component weights, means, and covariance matrices.The representation forbids duplicate components within a mixture.
Optimal transport plans: Optimal transport plans between Gaussian mixtures are usually not Gaussian mixtures; under absolute continuity, Proposition 3 proves this when the target is not an affine pushforward of the source.If the optimal plan were a Gaussian mixture, its components would be degenerate and force the transport map to be affine.
Exceptions and limitations: Gaussian-mixture optimal plans can occur when all source and target components are Dirac masses, whereas the general non-absolutely-continuous case is left partly conjectural.In the Dirac exception, the optimal plan is a Gaussian mixture of Dirac masses on R2d.
Barycenters: The barycenter between N(0, 1) and 1/2(δ−1 +δ1) is not a Gaussian mixture for t ∈(0, 1), because its density vanishes on (−t, t).This example supports the conjecture that barycenters of Gaussian mixtures are usually not Gaussian mixtures except at t = 0, 1.
Wasserstein-type distance: Restricting admissible transport plans to Gaussian mixtures ensures Gaussian-mixture barycenters and reduces the resulting optimization problem to a simple discrete formulation.The construction is presented as a well-defined Wasserstein-type distance between Gaussian mixtures.

4. MW2: a distance between Gaussian Mixture Models. … 4.4. Metric properties of MW2 and displacement interpolation.

MW2 restricts optimal-transport couplings between Gaussian mixtures to Gaussian mixture models, yielding a discrete formulation that is computationally simple. It is a metric and geodesic distance, with explicit displacement interpolations whose barycenters remain Gaussian mixtures with controlled component counts.

4.1. Definition of MW2.: MW2 is defined by restricting admissible couplings between two Gaussian mixtures to Gaussian mixture models, and it satisfies MW2(µ0, µ1) ≥ W2(µ0, µ1).The admissible set is nonempty because it contains the product measure µ0 ⊗ µ1.
4.2. An equivalent discrete formulation.: The continuous optimization is equivalent to a discrete linear program over component couplings, aggregating Wasserstein distances between Gaussian components.The equivalence follows by decomposing Gaussian-mixture couplings according to their source and target components.
4.2. An equivalent discrete formulation.: The quadratic-cost formulation is easy to compute because W2-optimal transport plans between Gaussian measures are explicit, and an optimizer exists with at most K0 + K1 −1 Gaussian components.The definition can also be generalized to other cost functions, although the quadratic cost is used for explicit Gaussian transport maps.
4.3. An example in one dimension.: In the one-dimensional example, the MW2 optimal transport plan is a mixture of three degenerate Gaussian measures supported on one-dimensional lines.The example compares transport plans for W2 and MW2 between two mixtures of two Gaussian components.
4.4.1. Metric properties of MW2.: MW2 defines a metric on GMMd(∞), and GMMd(∞) equipped with MW2 is a geodesic space.The metric proof uses symmetry, positivity, definiteness through W2, and a Gaussian-mixture-preserving gluing construction for the triangle inequality.
4.4.2. 1D and 2D barycenter examples.: In the one- and two-dimensional examples, MW2 barycenters are more regular than W2 barycenters and use fewer than three Gaussian components in the two-dimensional case.The one-dimensional MW2 barycenters are mixtures of at most 3 Gaussian components, while the two-dimensional geodesic has each barycenter as a mixture of less than three Gaussians.

4.5. Comparison between MW2 and W2.

This section compares MW2 with the classical Wasserstein distance W2, showing that MW2 can be strictly larger while identifying cases of equality and an upper bound involving component covariance traces. It also notes that the Gaussian-mixture methodology may require adaptation for other mixture families.

Comparison between MW2 and W2: MW2 is bounded below by W2, with equality when both mixtures are single Gaussians, finite Dirac combinations, or related by an affine transformation.The lower-bound equality is attained in each of these cases.
Comparison between MW2 and W2: MW2 can be strictly larger than W2 because Gaussian-mixture couplings approximating arbitrary couplings generally do not preserve the prescribed marginals.The restriction γ ∈ Π(µ0, µ1) creates this gap despite the density of Gaussian mixtures in P2(Rd).
Comparison between MW2 and W2: The squared MW2 distance decomposes into a W2 term between a Dirac mixture and one marginal plus a linear combination of component covariance traces.This decomposition provides the basis for an upper bound relating MW2 to W2 and the covariance traces of the two mixtures.
Comparison between MW2 and W2: For finite Dirac approximations converging in P2(Rd), the W2 term converges to W2, while Gaussian-to-Dirac approximation retains a nonzero covariance-dependent contribution.For a Gaussian N(m, Σ), the limiting contribution is (2trace(Σ))^1/2 ≠ 0.
Comparison between MW2 and W2: Extending the methodology beyond Gaussian mixtures is posed as an open direction for families such as Generalized Gaussian and t-distribution mixtures.Such extensions require addressing the main ingredients used by the Gaussian-mixture construction.

4.6. Generalization to other mixture models.

The framework extends from Gaussian mixtures to elliptical distribution families defined by a common contour function h. This family includes Gaussian, generalized Gaussian, and t-distributions, while retaining an explicit W2 distance when h is fixed.

4.6. Generalization to other mixture models.: The generalization considers elliptical distributions parameterized by a mean m, a positive definite symmetric matrix Σ, and a function h.The construction starts from the stated requirement and defines a family through these parameters.
4.6. Generalization to other mixture models.: Gaussian distributions correspond to h(t) = exp(−t/2), while generalized Gaussian distributions use h(t) = exp(−tβ).For generalized Gaussians, β need not equal 1.
4.6. Generalization to other mixture models.: T-distributions also belong to this family, with h(t) = (1 + t/ν)−(ν+d)/2.The passage presents t-distributions as another example of the elliptical family.
4.6. Generalization to other mixture models.: For a fixed h, the W2 distance between two distributions in the family can be computed explicitly.This explicit computation follows from the family’s elliptical contoured property.

5. Multi-marginal formulation and barycenters.

The section extends the Gaussian-mixture optimal transport problem to multiple marginals and links it to barycenters. It provides discrete formulations, a sparsity bound for barycenter components, and illustrative two-dimensional examples.

5.1. Multi-marginal formulation for MW2: The multi-marginal problem couples J Gaussian mixtures with positive weights λ0, …, λJ−1 summing to 1.The admissible couplings are probability measures on (R^d)^J with the prescribed mixtures as marginals.
5.1. Multi-marginal formulation for MW2: The continuous multi-marginal optimization can be rewritten as a discrete problem over nonnegative tensors w with prescribed discrete marginals.The tensor constraints require each discrete marginal to equal the corresponding mixture’s discrete weights.
5.1. Multi-marginal formulation for MW2: Computing the multi-marginal solution reduces to solving linear program (5.3) to obtain the optimal tensor w∗.The optimal multi-marginal plans are constructed from the resulting tensor using the component-level construction described earlier.
5.2. Link with the MW2-barycenters: An MW2 barycenter is obtained as ν∗ = B#γ∗, where γ∗ is an optimal plan for the multi-marginal problem (5.1).The barycenter map B is applied to the optimal multi-marginal coupling, establishing the link between the two formulations.
5.2. Link with the MW2-barycenters: The barycenter has less than K0 + · · · + KJ−1 − J + 1 non-zero coefficients when all involved covariance matrices are positive definite.This bound follows from the number of affine constraints in linear program (5.3).
5.2. Link with the MW2-barycenters: The MW2 barycenter problem differs from the usual W2 barycenter problem, whose barycenter may be approximated by Gaussian mixtures with arbitrarily high component counts.Although Gaussian mixtures are dense in P2(R^d), practical approximations can require many components.
5.3. Some examples: For four two-dimensional mixtures, each computed barycenter contains at most 11 components.The bound is K0 + K1 + K2 + K3 − 4 + 1 = 11, and thresholding the mixture densities produces barycenters between 2-D shapes.
5.3. Some examples: For more involved shapes represented by 12 Gaussian components each, estimated GMM symmetries are not necessarily preserved in the barycenters.The passage notes that symmetry can be enforced during GMM estimation to address this issue.

6. Using MW2 in practice.

The section extends MW2 to non-Gaussian-mixture data by first approximating measures with Gaussian mixtures and then computing MW2, while also introducing a relaxed KL-regularized formulation. It further discusses deterministic and random assignments derived from optimal transport plans, including their limitations.

Using MW2 in practice: Non-GMM data can be approximated by Gaussian mixtures, after which MW2 and its transport plan can displace the original data.The approximation enables use of MW2 and previously defined transport maps when the input distributions are not Gaussian mixtures.
Using MW2 in practice: MWK,2 approximates each probability measure by a K-component Gaussian mixture, using discrete log-likelihood or continuous KL minimization.For discrete data, Gaussian-mixture parameters can be inferred with the Expectation-Maximization algorithm; the discrete and continuous formulations coincide up to differential entropy.
Using MW2 in practice: The approximation-based MWK,2 is generally a pseudo-distance, and choosing K balances approximation quality against computational cost.Different distributions may share the same Gaussian-mixture approximation, although sufficiently large K can distinguish them; experiments generally use K = 10.
Using MW2 in practice: A relaxed formulation combines MW2 directly with KL divergences, with λ controlling the tradeoff between marginal fidelity and transport cost.As λ tends to infinity for discrete measures, the formulation approaches separate EM approximations; decreasing λ favors transport plans whose marginals are closer.
Using MW2 in practice: The relaxed problem can be optimized by gradient descent or automatic differentiation while projecting mixture weights and standard deviations onto their constraints.The implementation projects πk ≥0, σi,k ≥0 and Pk πk = 1 at each iteration.
Using MW2 in practice: The transport plan yields mean and random assignments, but the mean assignment need not be an optimal transport map or reproduce the target distribution.The random assignment reproduces the target measure in expectation, while defining it as a stochastic process over all of Rd is mathematically more difficult.

7. Two applications in image processing.

The paper applies MW2 to color transfer and texture synthesis, making high-dimensional transport plans and barycenters computationally easier while producing strong visual results. Color transfer uses Gaussian-mixture approximations of image color distributions, while texture synthesis applies MW2 to overlapping image patches.

Color transfer: MW2 is used for color transfer by approximating image color distributions with Gaussian mixtures and computing the MW2 map and Tmean.The transformed image retains the source content while its colors become closer to those of the target image.
Color transfer: K = 10 components provides the best practical color-transfer results by balancing mixture fidelity against transport-map regularity.Too few components inadequately represent complex color data, whereas more components do not necessarily improve results.
Color manipulation: MW2 barycenters between four 10-component color palettes modify one image so its palette spans the barycentric space between the four images.The barycenter weights are bilinear with respect to the four rectangle corners.
Texture synthesis: For texture synthesis, MW2 maps between Gaussian-mixture models of overlapping 3 × 3 color patches, producing results visually similar to the reference method with computational time approximately 10 times smaller.The experiments use K0 = K1 = 10, and extract approximately one patch per image pixel excluding borders.

8. Discussion and conclusion.

The discussion highlights the versatility of Gaussian mixture models for concrete and applied problems while identifying mixture estimation for discrete data as an important open question. The resulting estimates depend on the number of Gaussian components K and the parameter λ weighting data-fidelity terms.

Gaussian mixture models are versatile enough to represent large classes of concrete and applied problems.
Estimating mixtures for discrete data is identified as an important question raised by the framework and its generalization.
The obtained result depends on the number K of Gaussian components and the parameter λ weighting the data-fidelity terms.

Appendix: proofs. · Density of GMMd(∞) in Pp(Rd).

The appendix proves that GMMd(∞) is dense in Pp(Rd) under Wp for every p ≥ 1. The construction truncates the measure, covers a bounded ball by finitely many small balls, and maps each region to a representative point.

Density of GMMd(∞) in Pp(Rd).: For every p ≥ 1, GMMd(∞) is dense in Pp(Rd) with respect to Wp.This is the main result of the subsection.
Appendix: proofs.: The appendix provides a complete proof of density, adapted from Theorem 6.18 in.The proof is included for completeness.
Density of GMMd(∞) in Pp(Rd).: Given µ ∈ Pp(Rd) and ϵ > 0, the proof chooses a radius r so the p-moment contribution outside B(0,r) is at most ϵp.This controls the tail of µ before discretization.
Density of GMMd(∞) in Pp(Rd).: The bounded ball B(0,r) is covered by finitely many balls B(yk, ϵ), indexed by 1 ≤ k ≤ N.Finite covering reduces the approximation to finitely many representative centers.
Density of GMMd(∞) in Pp(Rd).: Disjoint sets Bk are formed from the covering balls while preserving coverage of B(0,r).The sets are defined by removing previously assigned covering regions.
Density of GMMd(∞) in Pp(Rd).: The map φ sends each y ∈ Bk ∩ B(0,r) to its center yk and sends points outside B(0,r) to 0.This produces a finite-valued approximation map.
Density of GMMd(∞) in Pp(Rd).: The construction concludes the density proof.The stated truncation and finite-center mapping complete the argument.

Identifiability properties of Gaussian mixture models.

Finite Gaussian mixtures are identifiable: equality of two mixtures forces equal component counts and, up to reordering, equal weights, means, and covariance matrices. The proof reduces the multivariate case to one-dimensional projections that preserve component distinctness outside measure-zero exceptional sets.

Proof strategy: In one dimension, the proof identifies a dominant Gaussian component from tail behavior, matches its variance, mean, and weight, then removes it recursively.When several components share the maximum variance, the one with the largest mean is selected for the tail comparison.
Proof strategy: For dimensions d > 1, projecting onto directions outside measure-zero exceptional sets makes the projected component pairs distinct, enabling the one-dimensional result.The projection maps means to inner products and covariances to quadratic forms; the one-dimensional identifiability conclusion then forces equality of the original parameters.
Identifiability result: Equality of two finite Gaussian mixtures implies equal numbers of components and matching weights, means, and covariance matrices after reordering.The component parameter triplets are equal as sets, with pairwise-distinct components within each mixture.