Gaussian mixtures closest to a given measure via optimal transport

Jean B. Lasserre

doi:10.5802/crmath.657

Article de recherche - Statistiques

Gaussian mixtures closest to a given measure via optimal transport

Jean B. Lasserre ¹

¹ LAAS-CNRS and Toulouse School of Economics (TSE), BP 54200, 7 Avenue du Colonel Roche, 31031 Toulouse cédex 4, France

Comptes Rendus. Mathématique, Volume 362 (2024), pp. 1455-1473.

Résumé
Abstract

Étant donné une mesure de probabilité (multivariée) $μ$ nous caractérisons les mélanges de Gaussiennes $ν_{ϕ}$ qui minimisent la distance de Wasserstein $W_{2} (μ, ν_{ϕ})$ quand la probabilité de mélange est sur un compact $S$ . (i) On montre d’abord que de telles probabilités de mélange sont solutions optimales d’un problème de transport où la marginale ( $ν_{ϕ}$ ) est elle-même une inconnue via la probabilité de mélange $ϕ$ . (ii) Ensuite en utilisant une propriété bien connue des Gaussiennes, ce problème de transport est lui-même vu comme un problème de moments généralisé. Si l’ensemble $S$ des paramètres admissibles est un semi-algébrique de base compact, alors on fournit un schéma numérique sans grille de discrétisation (la hiérarchie « moments – sommes-de-carrés »), pour approximer arbitrairement près la distance minimum optimale. Si la mesure $μ$ n’est pas un mélange de Gaussiennes (avec paramètres dans $S$ ) alors une distance strictement positive est détectée à une certaine relaxation de la hiérarchie. Si $μ$ est un mélange (fini) de Gaussiennes, alors une mesure de mélange atomique peut parfois être extraite de la solution optimale d’une relaxation quand la condition de « flatness » de Curto& Fiakow est satisfaite pour une matrice de moments.

Given a determinate (multivariate) probability measure $μ$ , we characterize Gaussian mixtures $ν_{ϕ}$ which minimize the Wasserstein distance $W_{2} (μ, ν_{ϕ})$ to $μ$ when the mixing probability measure $ϕ$ on the parameters $(m, Σ)$ 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 $ν_{ϕ}$ of the OT problem is also unknown via the mixing measure variable $ϕ$ . 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, Σ)$ 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 $μ$ is not a Gaussian mixture with parameters $(m, Σ) \in S$ , then a strictly positive distance is detected at a finite step of the hierarchy. If the original measure $μ$ is a Gaussian mixture with parameters $(m, Σ) \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.

Reçu le : 2023-12-24
Révisé le : 2024-04-23
Accepté le : 2024-06-13
Publié le : 2024-11-14

Zbl

DOI : 10.5802/crmath.657

Classification : 42C05, 47B32, 33C47, 90C23, 90C46
Keywords: Gaussian mixtures, Wasserstein distance, semidefinite relaxations, Moment-SOS hierarchy
Mots-clés : Mélanges de Gaussiennes, distance de Wasserstein, relaxations semidéfinies, hiérarchie moments-sommes-de-carrés

Affiliations des auteurs :

Jean B. Lasserre ¹

¹ LAAS-CNRS and Toulouse School of Economics (TSE), BP 54200, 7 Avenue du Colonel Roche, 31031 Toulouse cédex 4, France

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{CRMATH_2024__362_G11_1455_0,
     author = {Jean B. Lasserre},
     title = {Gaussian mixtures closest to a given measure via optimal transport},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1455--1473},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {362},
     year = {2024},
     doi = {10.5802/crmath.657},
     zbl = {07945488},
     language = {en},
}

TY  - JOUR
AU  - Jean B. Lasserre
TI  - Gaussian mixtures closest to a given measure via optimal transport
JO  - Comptes Rendus. Mathématique
PY  - 2024
SP  - 1455
EP  - 1473
VL  - 362
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.657
LA  - en
ID  - CRMATH_2024__362_G11_1455_0
ER  -

%0 Journal Article
%A Jean B. Lasserre
%T Gaussian mixtures closest to a given measure via optimal transport
%J Comptes Rendus. Mathématique
%D 2024
%P 1455-1473
%V 362
%I Académie des sciences, Paris
%R 10.5802/crmath.657
%G en
%F CRMATH_2024__362_G11_1455_0

Jean B. Lasserre. Gaussian mixtures closest to a given measure via optimal transport. Comptes Rendus. Mathématique, Volume 362 (2024), pp. 1455-1473. doi : 10.5802/crmath.657. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.657/

Bibliographie
Cité par

[1] Carlos Améndola; Jean-Charles Faugère; Bernd Sturmfels Moment varieties of Gaussian mixtures, J. Algebr. Stat., Volume 7 (2016) no. 1, pp. 14-28 | DOI | MR | Zbl

[2] Handbook on semidefinite, conic and polynomial optimization (Miguel F. Anjos; Jean B. Lasserre, eds.), International Series in Operations Research & Management Science, 166, Springer, 2012, xii+960 pages | DOI | MR | Zbl

[3] Carlos Améndola; Kristian Ranestad; Bernd Sturmfels Algebraic identifiability of Gaussian mixtures, Int. Math. Res. Not., Volume 2018 (2018) no. 21, pp. 6556-6580 | DOI | MR | Zbl

[4] Xing Bin; F. Bunea; J. Niles-Wred Estimation and inference for the Wasserstein distance between mixing measures in topic models (2023) (https://arxiv.org/abs/2206.12768)

[5] Ainesh Bakshi; Ilias Diakonikolas; He Jia; Daniel M. Kane; Pravesh K. Kothari; Santosh S. Vempala Robustly learning mixtures of $k$ arbitrary Gaussians, STOC ’22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery (2022), pp. 1234-1247 | DOI | MR | Zbl

[6] Charles F. Dunkl; Yuan Xu Orthogonal polynomials of several variables, Encyclopedia of Mathematics and Its Applications, 81, Cambridge University Press, 2001, xvi+390 pages | DOI | MR | Zbl

[7] Marco Di Zio; Ugo Guarnera; Roberto Rocci A mixture of mixture models for a classification problem: the unity measure error, Comput. Stat. Data Anal., Volume 51 (2007) no. 5, pp. 2573-2585 | DOI | MR | Zbl

[8] Philippe Heinrich; Jonas Kahn Strong identifiability and optimal minimax rates for finite mixture estimation, Ann. Stat., Volume 46 (2018) no. 6A, pp. 2844-2870 | DOI | MR | Zbl

[9] Didier Henrion; Milan Korda; Jean B. Lasserre The moment-SOS hierarchy—lectures in probability, statistics, computational geometry, control and nonlinear PDEs, Series on Optimization and its Applications, 4, World Scientific, 2021, xvii+229 pages | MR | Zbl

[10] Didier Henrion; Jean B. Lasserre; Johan Löfberg GloptiPoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., Volume 24 (2009) no. 4-5, pp. 761-779 | DOI | MR | Zbl

[11] Adam Tauman Kalai; Ankur Moitra; Gregory Valiant Efficiently learning mixtures of two Gaussians, STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, Association for Computing Machinery (2010), pp. 553-562 | DOI | MR | Zbl

[12] Pravesh K. Kothari; Peter Manohar; Brian Hu Zhang Polynomial-time sum-of-squares can robustly estimate mean and covariance of Gaussians optimally, Proceedings of The 33rd International Conference on Algorithmic Learning Theory (Sanjoy Dasgupta; Nika Haghtalab, eds.) (Proceedings of Machine Learning Research), Volume 167, PMLR (2022), pp. 638-667 | MR

[13] Jean B. Lasserre Moments, positive polynomials and their applications, Imperial College Press Optimization Series, 1, Imperial College Press, 2010, xxii+361 pages | MR | Zbl

[14] Jean B. Lasserre The existence of Gaussian cubature formulas, J. Approx. Theory, Volume 164 (2012) no. 5, pp. 572-585 | DOI | MR | Zbl

[15] Jean B. Lasserre An introduction to polynomial and semi-algebraic optimization, Cambridge Texts in Applied Mathematics, Cambridge University Press, 2015, xiv+339 pages | DOI | MR | Zbl

[16] Bruce G. Lindsay Moment matrices: applications in mixtures, Ann. Stat., Volume 17 (1989) no. 2, pp. 722-740 | DOI | MR | Zbl

[17] Geoffrey McLachlan; David Peel Finite mixture models, Wiley Ser. Probab. Math. Stat., John Wiley & Sons, 2000 | DOI | MR | Zbl

[18] Ankur Moitra; Gregory Valiant Settling the polynomial learnability of mixtures of Gaussians, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science—FOCS 2010, IEEE Computer Society (2010), pp. 93-102 | DOI | MR

[19] J. S. Marron; M. P. Wand Exact mean integrated squared error, Ann. Stat., Volume 20 (1992) no. 2, pp. 712-736 | DOI | MR | Zbl

[20] H. Michael Möller On square positive extensions and cubature formulas, J. Comput. Appl. Math., Volume 199 (2007) no. 1, pp. 80-88 | DOI | MR | Zbl

[21] XuanLong Nguyen Convergence of latent mixing measures in finite and infinite mixture models, Ann. Stat., Volume 41 (2013) no. 1, pp. 370-400 | DOI | MR | Zbl

[22] Ryan O’Donnell SOS is not obviously automatizable, even approximately, 8th Innovations in Theoretical Computer Science Conference (LIPIcs. Leibniz Int. Proc. Inform.), Volume 67, Schloss Dagstuhl. Leibniz-Zent. Inform., 2017 (No. 59, 10 pages) | DOI | MR | Zbl

[23] Haim Permuter; Joseph Francos; Ian Jermyn A study of Gaussian mixture models of color and texture features for image classification and segmentation, Pattern Recognition, Volume 39 (2006) no. 4, pp. 695-706 | DOI | Zbl

[24] Mihai Putinar Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., Volume 42 (1993) no. 3, pp. 969-984 | DOI | MR | Zbl

[25] Jin Wang Generating daily changes in market variables using a multivariate mixture of normal distributions, Proceeding of the 2001 Winter Simulation Conference (Cat. No.01CH37304) (2001), pp. 283-289 | DOI

[26] Yihong Wu; Pengkun Yang Optimal estimation of Gaussian mixtures via denoised method of moments, Ann. Stat., Volume 48 (2020) no. 4, pp. 1981-2007 | DOI | MR | Zbl

[27] Guoshen Yu; Guillermo Sapiro; Stéphane Mallat Solving inverse problems with piecewise linear estimators: from Gaussian mixture models to structured sparsity, IEEE Trans. Image Process., Volume 21 (2012) no. 5, pp. 2481-2499 | DOI | MR | Zbl

Cité par Sources :

Commentaires - Politique