{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T05:46:00Z","timestamp":1761198360715},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T00:00:00Z","timestamp":1718064000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T00:00:00Z","timestamp":1718064000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer. Math."],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Most common optimal transport (OT) solvers are currently based on an approximation of underlying measures by discrete measures. However, it is sometimes relevant to work only with moments of measures instead of the measure itself, and many common OT problems can be formulated as moment problems (the most relevant examples being <jats:inline-formula><jats:alternatives><jats:tex-math>$$L^p$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>L<\/mml:mi>\n                    <mml:mi>p<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Wasserstein distances, barycenters, and Gromov\u2013Wasserstein discrepancies on Euclidean spaces). We leverage this fact to develop a generalized moment formulation that covers these classes of OT problems. The transport plan is represented through its moments on a given basis, and the marginal constraints are expressed in terms of moment constraints. A practical computation then consists in considering a truncation of the involved moment sequences up to a certain order, and using the polynomial sums-of-squares hierarchy for measures supported on semi-algebraic sets. We prove that the strategy converges to the solution of the OT problem as the order increases. We also show how to approximate linear quantities of interest, and how to estimate the support of the optimal transport map from the computed moments using Christoffel\u2013Darboux kernels.  Numerical experiments illustrate the good behavior of the approach.<\/jats:p>","DOI":"10.1007\/s00211-024-01422-x","type":"journal-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T15:31:27Z","timestamp":1718119887000},"page":"1541-1578","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Moment-SoS methods for optimal transport problems"],"prefix":"10.1007","volume":"156","author":[{"given":"Olga","family":"Mula","sequence":"first","affiliation":[]},{"given":"Anthony","family":"Nouy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"1422_CR1","unstructured":"Carlier, G.: Optimal transportation and economic applications. Lecture Notes 18 (2012)"},{"issue":"2","key":"1422_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/ectj.12083","volume":"20","author":"A Galichon","year":"2017","unstructured":"Galichon, A.: A survey of some recent applications of optimal transport methods to econometrics. Econom. J. 20(2), 1\u201311 (2017)","journal-title":"Econom. J."},{"issue":"1","key":"1422_CR3","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s00526-014-0803-0","volume":"54","author":"C Cotar","year":"2015","unstructured":"Cotar, C., Friesecke, G., Pass, B.: Infinite-body optimal transport with coulomb cost. Calc. Var. Partial Differ. Equ. 54(1), 717\u2013742 (2015)","journal-title":"Calc. Var. Partial Differ. Equ."},{"key":"1422_CR4","doi-asserted-by":"crossref","unstructured":"Benamou, J.-D., Carlier, G., Nenna, L.: A numerical method to solve multi-marginal optimal transport problems with coulomb cost. In: Splitting Methods in Communication. Imaging, Science, and Engineering, pp. 577\u2013601. Springer, Cham (2017)","DOI":"10.1007\/978-3-319-41589-5_17"},{"issue":"2","key":"1422_CR5","doi-asserted-by":"publisher","first-page":"1385","DOI":"10.1137\/15M1050264","volume":"49","author":"G Carlier","year":"2017","unstructured":"Carlier, G., Duval, V., Peyr\u00e9, G., Schmitzer, B.: Convergence of entropic schemes for optimal transport and gradient flows. SIAM J. Math. Anal. 49(2), 1385\u20131418 (2017)","journal-title":"SIAM J. Math. Anal."},{"issue":"5\u20136","key":"1422_CR6","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1561\/2200000073","volume":"11","author":"G Peyr\u00e9","year":"2019","unstructured":"Peyr\u00e9, G., Cuturi, M.: Computational optimal transport: with applications to data science. Found. Trends\u00ae Mach. Learn. 11(5\u20136), 355\u2013607 (2019)","journal-title":"Found. Trends\u00ae Mach. Learn."},{"key":"1422_CR7","unstructured":"Cuturi, M.: Sinkhorn distances: lightspeed computation of optimal transport. In: Advances in Neural Information Processing Systems, pp. 2292\u20132300 (2013)"},{"issue":"314","key":"1422_CR8","doi-asserted-by":"publisher","first-page":"2563","DOI":"10.1090\/mcom\/3303","volume":"87","author":"L Chizat","year":"2018","unstructured":"Chizat, L., Peyr\u00e9, G., Schmitzer, B., Vialard, F.-X.: Scaling algorithms for unbalanced optimal transport problems. Math. Comput. 87(314), 2563\u20132609 (2018)","journal-title":"Math. Comput."},{"issue":"1","key":"1422_CR9","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02216923","volume":"20","author":"DP Bertsekas","year":"1989","unstructured":"Bertsekas, D.P., Castanon, D.A.: The auction algorithm for the transportation problem. Ann. Oper. Res. 20(1), 67\u201396 (1989)","journal-title":"Ann. Oper. Res."},{"issue":"4","key":"1422_CR10","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1007\/s10208-017-9355-y","volume":"18","author":"TO Gallou\u00ebt","year":"2018","unstructured":"Gallou\u00ebt, T.O., M\u00e9rigot, Q.: A Lagrangian scheme \u00e0 la Brenier for the incompressible Euler equations. Found. Comput. Math. 18(4), 835\u2013865 (2018)","journal-title":"Found. Comput. Math."},{"issue":"5","key":"1422_CR11","doi-asserted-by":"publisher","first-page":"1583","DOI":"10.1111\/j.1467-8659.2011.02032.x","volume":"30","author":"Q M\u00e9rigot","year":"2011","unstructured":"M\u00e9rigot, Q.: A multiscale approach to optimal transport. Comput. Graph. Forum 30(5), 1583\u20131592 (2011)","journal-title":"Comput. Graph. Forum"},{"issue":"2","key":"1422_CR12","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/s10851-016-0653-9","volume":"56","author":"B Schmitzer","year":"2016","unstructured":"Schmitzer, B.: A sparse multiscale algorithm for dense optimal transport. J. Math. Imaging Vis. 56(2), 238\u2013259 (2016)","journal-title":"J. Math. Imaging Vis."},{"issue":"3","key":"1422_CR13","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s002110050002","volume":"84","author":"JD Benamou","year":"2000","unstructured":"Benamou, J.D., Brenier, Y.: A computational fluid mechanics solution to the Monge\u2013Kantorovich mass transfer problem. Numer. Math. 84(3), 375\u2013393 (2000)","journal-title":"Numer. Math."},{"issue":"3","key":"1422_CR14","doi-asserted-by":"publisher","first-page":"1632","DOI":"10.1137\/21M140732X","volume":"44","author":"G Friesecke","year":"2022","unstructured":"Friesecke, G., Schulz, A.S., V\u00f6gler, D.: Genetic column generation: fast computation of high-dimensional multimarginal optimal transport problems. SIAM J. Sci. Comput. 44(3), 1632\u20131654 (2022)","journal-title":"SIAM J. Sci. Comput."},{"issue":"1","key":"1422_CR15","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/S0378-4754(00)00270-6","volume":"55","author":"IM Sobol","year":"2001","unstructured":"Sobol, I.M.: Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates. Math. Comput. Simul. 55(1), 271\u2013280 (2001)","journal-title":"Math. Comput. Simul."},{"issue":"1","key":"1422_CR16","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1093\/imaiai\/iau001","volume":"3","author":"AB Owen","year":"2014","unstructured":"Owen, A.B., Dick, J., Chen, S.: Higher order Sobol\u2019 indices. Inf. Inference 3(1), 59\u201381 (2014)","journal-title":"Inf. Inference"},{"issue":"1","key":"1422_CR17","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1214\/18-AOS1683","volume":"47","author":"Y De Castro","year":"2019","unstructured":"De Castro, Y., Gamboa, F., Henrion, D., Hess, R., Lasserre, J.-B.: Approximate optimal designs for multivariate polynomial regression. Ann. Stat. 47(1), 127\u2013155 (2019)","journal-title":"Ann. Stat."},{"key":"1422_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/9781108937078","volume-title":"The Christoffel\u2013Darboux Kernel for Data Analysis","author":"JB Lasserre","year":"2022","unstructured":"Lasserre, J.B., Pauwels, E., Putinar, M.: The Christoffel\u2013Darboux Kernel for Data Analysis. Cambridge University Press, Cambridge (2022)"},{"key":"1422_CR19","unstructured":"Roos\u00a0Hoefgeest, P., Slot, L.: The Christoffel\u2013Darboux kernel for topological data analysis. In: 39th International Symposium on Computational Geometry (SoCG 2023) (2023). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"1","key":"1422_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcp.2006.01.038","volume":"218","author":"M Frank","year":"2006","unstructured":"Frank, M., Dubroca, B., Klar, A.: Partial moment entropy approximation to radiative heat transfer. J. Comput. Phys. 218(1), 1\u201318 (2006)","journal-title":"J. Comput. Phys."},{"key":"1422_CR21","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1140\/epjd\/e2010-00190-8","volume":"60","author":"B Dubroca","year":"2010","unstructured":"Dubroca, B., Feugeas, J.-L., Frank, M.: Angular moment model for the Fokker\u2013Planck equation. Eur. Phys. J. D 60, 301\u2013307 (2010)","journal-title":"Eur. Phys. J. D"},{"key":"1422_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.5802\/smai-jcm.93","volume":"9","author":"GW Alldredge","year":"2023","unstructured":"Alldredge, G.W., Frank, M., Giesselmann, J.: On the convergence of the regularized entropy-based moment method for kinetic equations. SMAI J. Comput. Math. 9, 1\u201329 (2023)","journal-title":"SMAI J. Comput. Math."},{"issue":"1","key":"1422_CR23","doi-asserted-by":"publisher","first-page":"113","DOI":"10.3934\/mcrf.2019032","volume":"10","author":"S Marx","year":"2020","unstructured":"Marx, S., Weisser, T., Henrion, D., Lasserre, J.-B.: A moment approach for entropy solutions to nonlinear hyperbolic PDEs. MCRF 10(1), 113\u2013140 (2020)","journal-title":"MCRF"},{"key":"1422_CR24","doi-asserted-by":"crossref","unstructured":"Cardoen, C., Marx, S., Nouy, A., Seguin, N.: A moment approach for entropy solutions of parameter-dependent hyperbolic conservation laws. arXiv preprint arXiv:2307.10043 (2023)","DOI":"10.1007\/s00211-024-01428-5"},{"issue":"3","key":"1422_CR25","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1214\/10-AOP571","volume":"39","author":"A Gloria","year":"2011","unstructured":"Gloria, A., Otto, F.: An optimal variance estimate in stochastic homogenization of discrete elliptic equations. Ann. Probab. 39(3), 779\u2013856 (2011)","journal-title":"Ann. Probab."},{"key":"1422_CR26","doi-asserted-by":"publisher","DOI":"10.1002\/9781118481844","volume-title":"The Stochastic Perturbation Method for Computational Mechanics","author":"M Kaminski","year":"2013","unstructured":"Kaminski, M.: The Stochastic Perturbation Method for Computational Mechanics. Wiley, Hoboken (2013)"},{"issue":"1","key":"1422_CR27","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s10107-006-0085-1","volume":"112","author":"JB Lasserre","year":"2008","unstructured":"Lasserre, J.B.: A semidefinite programming approach to the generalized problem of moments. Math. Program. 112(1), 65\u201392 (2008)","journal-title":"Math. Program."},{"key":"1422_CR28","unstructured":"Catala, P.: Positive semidefinite relaxations for imaging science. PhD thesis, PSL University (2020)"},{"key":"1422_CR29","doi-asserted-by":"crossref","unstructured":"Henrion, D., Lasserre, J.B.: Graph recovery from incomplete moment information. Constr. Approx. 1\u201323 (2022)","DOI":"10.1007\/s00365-022-09563-8"},{"issue":"3","key":"1422_CR30","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s00365-021-09535-4","volume":"54","author":"S Marx","year":"2021","unstructured":"Marx, S., Pauwels, E., Weisser, T., Henrion, D., Lasserre, J.B.: Semi-algebraic approximation using Christoffel\u2013Darboux kernel. Constr. Approx. 54(3), 391\u2013429 (2021)","journal-title":"Constr. Approx."},{"issue":"328","key":"1422_CR31","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1090\/mcom\/3568","volume":"90","author":"A Alfonsi","year":"2021","unstructured":"Alfonsi, A., Coyaud, R., Ehrlacher, V., Lombardi, D.: Approximation of optimal transport problems with marginal moments constraints. Math. Comput. 90(328), 689\u2013737 (2021)","journal-title":"Math. Comput."},{"key":"1422_CR32","unstructured":"Vacher, A., Muzellec, B., Rudi, A., Bach, F., Vialard, F.-X.: A dimension-free computational upper-bound for smooth optimal transport estimation. In: Conference on Learning Theory, pp. 4143\u20134173 (2021). PMLR"},{"key":"1422_CR33","unstructured":"Muzellec, B., Vacher, A., Bach, F., Vialard, F.-X., Rudi, A.: Near-optimal estimation of smooth transport maps with kernel sums-of-squares. arXiv preprint arXiv:2112.01907 (2021)"},{"key":"1422_CR34","doi-asserted-by":"crossref","DOI":"10.1142\/p665","volume-title":"Moments, Positive Polynomials and Their Applications","author":"JB Lasserre","year":"2009","unstructured":"Lasserre, J.B.: Moments, Positive Polynomials and Their Applications, vol. 1. World Scientific Publishing Company, London (2009)"},{"key":"1422_CR35","doi-asserted-by":"crossref","unstructured":"Schm\u00fcdgen, K.: The moment problem on compact semi-algebraic sets. In: The Moment Problem, pp. 283\u2013313. Springer, Cham (2017)","DOI":"10.1007\/978-3-319-64546-9_12"},{"issue":"3","key":"1422_CR36","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1512\/iumj.1993.42.42045","volume":"42","author":"M Putinar","year":"1993","unstructured":"Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42(3), 969\u2013984 (1993)","journal-title":"Indiana Univ. Math. J."},{"key":"1422_CR37","volume-title":"Topics in Optimal Transportation","author":"C Villani","year":"2003","unstructured":"Villani, C.: Topics in Optimal Transportation, vol. 58. American Mathematical Soc, Providence (2003)"},{"issue":"2","key":"1422_CR38","doi-asserted-by":"publisher","first-page":"904","DOI":"10.1137\/100805741","volume":"43","author":"M Agueh","year":"2011","unstructured":"Agueh, M., Carlier, G.: Barycenters in the Wasserstein space. SIAM J. Math. Anal. 43(2), 904\u2013924 (2011)","journal-title":"SIAM J. Math. Anal."},{"key":"1422_CR39","unstructured":"Alvarez-Melis, D., Jegelka, S., Jaakkola, T.S.: Towards optimal transport with global invariances. In: The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1870\u20131879 (2019). PMLR"},{"issue":"4","key":"1422_CR40","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s10208-011-9093-5","volume":"11","author":"F M\u00e9moli","year":"2011","unstructured":"M\u00e9moli, F.: Gromov\u2013Wasserstein distances and the metric approach to object matching. Found. Comput. Math. 11(4), 417\u2013487 (2011)","journal-title":"Found. Comput. Math."},{"issue":"4","key":"1422_CR41","first-page":"2753","volume":"12","author":"F Beier","year":"2023","unstructured":"Beier, F., Beinert, R., Steidl, G.: Multi-marginal Gromov\u2013Wasserstein transport and barycenters. Inf. Inference J. IMA 12(4), 2753\u20132781 (2023)","journal-title":"Inf. Inference J. IMA"},{"key":"1422_CR42","unstructured":"Peyr\u00e9, G., Cuturi, M., Solomon, J.: Gromov\u2013Wasserstein averaging of kernel and distance matrices. In: International Conference on Machine Learning, pp. 2664\u20132672 (2016). PMLR"},{"key":"1422_CR43","unstructured":"Dumont, T., Lacombe, T., Vialard, F.-X.: On the existence of Monge maps for the Gromov\u2013Wasserstein problem (2022)"},{"issue":"1","key":"1422_CR44","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s10208-020-09451-2","volume":"21","author":"E Pauwels","year":"2021","unstructured":"Pauwels, E., Putinar, M., Lasserre, J.B.: Data analysis from empirical moments and the Christoffel function. Found. Comput. Math. 21(1), 243\u2013273 (2021)","journal-title":"Found. Comput. Math."},{"key":"1422_CR45","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1051\/ps\/2022003","volume":"26","author":"MT Vu","year":"2022","unstructured":"Vu, M.T., Bachoc, F., Pauwels, E.: Rate of convergence for geometric inference based on the empirical Christoffel function. ESAIM Probab. Stat. 26, 171\u2013207 (2022)","journal-title":"ESAIM Probab. Stat."},{"key":"1422_CR46","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107786134","volume-title":"Orthogonal Polynomials of Several Variables","author":"CF Dunkl","year":"2014","unstructured":"Dunkl, C.F., Xu, Y.: Orthogonal Polynomials of Several Variables. Cambridge University Press, Cambridge (2014)"},{"issue":"3","key":"1422_CR47","doi-asserted-by":"publisher","first-page":"1439","DOI":"10.1007\/s10444-019-09673-1","volume":"45","author":"JB Lasserre","year":"2019","unstructured":"Lasserre, J.B., Pauwels, E.: The empirical Christoffel function with applications in data analysis. Adv. Comput. Math. 45(3), 1439\u20131468 (2019)","journal-title":"Adv. Comput. Math."},{"key":"1422_CR48","unstructured":"Feydy, J., S\u00e9journ\u00e9, T., Vialard, F.-X., Amari, S.-I., Trouv\u00e9, A., Peyr\u00e9, G.: Interpolating between optimal transport and MMD using Sinkhorn divergences. In: The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2681\u20132690 (2019). PMLR"},{"key":"1422_CR49","unstructured":"Nouy, A., Grelier, E., Giraldi, L.: ApproximationToolbox. 10.5281\/zenodo.3653971"},{"issue":"4\u20135","key":"1422_CR50","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1080\/10556780802699201","volume":"24","author":"D Henrion","year":"2009","unstructured":"Henrion, D., Lasserre, J.-B., L\u00f6fberg, J.: Gloptipoly 3: moments, optimization and semidefinite programming. Optim. Methods Softw. 24(4\u20135), 761\u2013779 (2009)","journal-title":"Optim. Methods Softw."}],"container-title":["Numerische Mathematik"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00211-024-01422-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00211-024-01422-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00211-024-01422-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,27]],"date-time":"2024-07-27T17:02:48Z","timestamp":1722099768000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00211-024-01422-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,11]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["1422"],"URL":"https:\/\/doi.org\/10.1007\/s00211-024-01422-x","relation":{},"ISSN":["0029-599X","0945-3245"],"issn-type":[{"value":"0029-599X","type":"print"},{"value":"0945-3245","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,11]]},"assertion":[{"value":"5 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 April 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}