A Unified Framework for Gaussian Mixture Reduction with Composite Transportation Distance

Qiong Zhang, Jiahua Chen

Abstract

Gaussian mixture reduction (GMR) is the problem of approximating a finite Gaussian mixture by one with fewer components. It is widely used in density estimation, nonparametric belief propagation, and Bayesian recursive filtering. Although optimization and clustering-based algorithms have been proposed for GMR, they are either computationally expensive or lacking in theoretical supports. In this work, we propose to perform GMR by minimizing the entropic regularized composite transportation distance between two mixtures. We show our approach provides a unified framework for GMR that is both interpretable and computationally efficient. Our work also bridges the gap between optimization and clustering-based approaches for GMR. A Majorization-Minimization algorithm is developed for our optimization problem and its theoretical convergence is also established in this paper. Empirical experiments are also conducted to show the effectiveness of GMR. The effect of the choice of transportation cost on the performance of GMR is also investigated.

Introduction

Gaussian Mixture Models (GMMs) are fundamental tools in probabilistic modeling, yet they face a scalability challenge in recursive applications like Bayesian filtering or belief propagation. In these scenarios, the number of components often grows exponentially over time, making computation intractable. Gaussian Mixture Reduction (GMR) addresses this by approximating a high-order mixture with a simpler one containing fewer components.

Historically, GMR methods fell into two camps: rigorous but slow optimization-based methods (e.g., minimizing $L_2$ distance) and fast but theoretically opaque clustering-based heuristics. This research introduces a unified framework that bridges this gap, offering both mathematical rigor and high computational efficiency.

Methodology: Composite Transportation Divergence

The core of the proposed approach is the Composite Transportation Divergence (CTD). By treating a GMM as a discrete distribution where each "point" is a Gaussian component, the authors frame GMR as an optimal transport problem. This allows for a principled way to "collapse" mass from the original components into a smaller target set.

Visualizing GMR: The original mixture with 8 components (left) is approximated by a reduced mixture with only 3 components (right) while preserving the overall density shape.

The Majorization-Minimization (MM) Algorithm

To solve the resulting optimization problem, the authors developed a Majorization-Minimization algorithm:

  1. Majorization Step: Find an optimal transportation plan that dictates how probability mass moves from the original components to the reduced ones.
  2. Minimization Step: Update the parameters (means and covariances) of the reduced components to minimize the transportation cost.

A key insight is that many common clustering-based GMR methods are actually special cases of this framework (e.g., "hard clustering" corresponds to zero regularization). This provides the first rigorous convergence proof for these widely used heuristics.

Experimental Evaluation

The framework was tested across three domains:

  • Simulated Mixtures: Demonstrated that the CTD-based method achieves accuracy comparable to the gold-standard "Minimum ISE" approach while being 10x to 1,000x faster.
  • Belief Propagation: Successfully maintained tractability in a synthetic graphical model where exact inference was impossible.
  • Hand Gesture Recognition: Using the Jochen Triesch database, the method created efficient "class prototypes," achieving up to 93.5% accuracy with significantly reduced computational overhead during testing.

Conclusion and Future Work

This unified framework provides a theoretically sound and practically efficient solution for GMR. While the algorithm currently requires a pre-specified number of target components ($M$) and can be sensitive to initialization, it marks a significant step forward in making complex density estimation tasks more manageable. Future research may explore automated selection of $M$ and extensions to non-Gaussian mixtures.

Summary updated

Abstract

Gaussian mixture reduction (GMR) is the problem of approximating a finite Gaussian mixture by one with fewer components. It is widely used in density estimation, nonparametric belief propagation, and Bayesian recursive filtering. Although optimization and clustering-based algorithms have been proposed for GMR, they are either computationally expensive or lacking in theoretical supports. In this work, we propose to perform GMR by minimizing the entropic regularized composite transportation distance between two mixtures. We show our approach provides a unified framework for GMR that is both interpretable and computationally efficient. Our work also bridges the gap between optimization and clustering-based approaches for GMR. A Majorization-Minimization algorithm is developed for our optimization problem and its theoretical convergence is also established in this paper. Empirical experiments are also conducted to show the effectiveness of GMR. The effect of the choice of transportation cost on the performance of GMR is also investigated.
BibTeX
@article{zhang2024unified,
  author = {Qiong Zhang and Jiahua Chen},
  title = {{A Unified Framework for Gaussian Mixture Reduction with Composite Transportation Distance}},
  journal = {IEEE Trans. Information Theory},
  year = {2024},
  url = {https://openreview.net/forum?id=FJnsWQSAFs},
}
Figure