{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T18:10:02Z","timestamp":1728583802143},"reference-count":13,"publisher":"American Mathematical Society (AMS)","issue":"351","license":[{"start":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:00:00Z","timestamp":1742947200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["TRR 109","Collaborative Research Center TRR 109 \u00e2??Discretization in Geometry and Dynamics\u00e2??","project number 195170736"],"award-info":[{"award-number":["TRR 109","Collaborative Research Center TRR 109 \u00e2??Discretization in Geometry and Dynamics\u00e2??","project number 195170736"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>The recently introduced Genetic Column Generation (GenCol) algorithm has been numerically observed to efficiently and accurately compute high-dimensional optimal transport (OT) plans for general multi-marginal problems, but theoretical results on the algorithm have hitherto been lacking. The algorithm solves the OT linear program on a dynamically updated low-dimensional submanifold consisting of sparse plans. The submanifold dimension exceeds the sparse support of optimal plans only by a fixed factor <inline-formula content-type=\"math\/mathml\">\n<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"beta\">\n  <mml:semantics>\n    <mml:mi>\u03b2<\/mml:mi>\n    <mml:annotation encoding=\"application\/x-tex\">\\beta<\/mml:annotation>\n  <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>. Here we prove that for <inline-formula content-type=\"math\/mathml\">\n<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"beta greater-than-or-equal-to 2\">\n  <mml:semantics>\n    <mml:mrow>\n      <mml:mi>\u03b2<\/mml:mi>\n      <mml:mo>\u2265<\/mml:mo>\n      <mml:mn>2<\/mml:mn>\n    <\/mml:mrow>\n    <mml:annotation encoding=\"application\/x-tex\">\\beta \\geq 2<\/mml:annotation>\n  <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> and in the two-marginal case, GenCol always converges to an exact solution, for arbitrary costs and marginals. The proof relies on the concept of c-cyclical monotonicity. As an offshoot, GenCol rigorously reduces the data complexity of numerically solving two-marginal OT problems from <inline-formula content-type=\"math\/mathml\">\n<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis script l squared right-parenthesis\">\n  <mml:semantics>\n    <mml:mrow>\n      <mml:mi>O<\/mml:mi>\n      <mml:mo stretchy=\"false\">(<\/mml:mo>\n      <mml:msup>\n        <mml:mi>\u2113<\/mml:mi>\n        <mml:mn>2<\/mml:mn>\n      <\/mml:msup>\n      <mml:mo stretchy=\"false\">)<\/mml:mo>\n    <\/mml:mrow>\n    <mml:annotation encoding=\"application\/x-tex\">O(\\ell ^2)<\/mml:annotation>\n  <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> to <inline-formula content-type=\"math\/mathml\">\n<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis script l right-parenthesis\">\n  <mml:semantics>\n    <mml:mrow>\n      <mml:mi>O<\/mml:mi>\n      <mml:mo stretchy=\"false\">(<\/mml:mo>\n      <mml:mi>\u2113<\/mml:mi>\n      <mml:mo stretchy=\"false\">)<\/mml:mo>\n    <\/mml:mrow>\n    <mml:annotation encoding=\"application\/x-tex\">O(\\ell )<\/mml:annotation>\n  <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> without any loss in accuracy, where <inline-formula content-type=\"math\/mathml\">\n<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script l\">\n  <mml:semantics>\n    <mml:mi>\u2113<\/mml:mi>\n    <mml:annotation encoding=\"application\/x-tex\">\\ell<\/mml:annotation>\n  <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> is the number of discretization points for a single marginal. At the end of the paper we also present some insights into the convergence behavior in the multi-marginal case.<\/p>","DOI":"10.1090\/mcom\/3968","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T17:54:00Z","timestamp":1711475640000},"page":"263-275","source":"Crossref","is-referenced-by-count":0,"title":["Convergence proof for the GenCol algorithm in the case of two-marginal optimal transport"],"prefix":"10.1090","volume":"94","author":[{"given":"Gero","family":"Friesecke","sequence":"first","affiliation":[]},{"given":"Maximilian","family":"Penka","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"1","doi-asserted-by":"publisher","first-page":"Paper No. 100669, 21","DOI":"10.1016\/j.disopt.2021.100669","article-title":"Hardness results for multimarginal optimal transport problems","volume":"42","author":"Altschuler, Jason M.","year":"2021","journal-title":"Discrete Optim.","ISSN":"http:\/\/id.crossref.org\/issn\/1572-5286","issn-type":"print"},{"issue":"4","key":"2","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1002\/cpa.3160440402","article-title":"Polar factorization and monotone rearrangement of vector-valued functions","volume":"44","author":"Brenier, Yann","year":"1991","journal-title":"Comm. Pure Appl. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/0010-3640","issn-type":"print"},{"issue":"1","key":"3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1287\/moor.2015.0714","article-title":"The cutting plane method is polynomial for perfect matchings","volume":"41","author":"Chandrasekaran, Karthekeyan","year":"2016","journal-title":"Math. Oper. Res.","ISSN":"http:\/\/id.crossref.org\/issn\/0364-765X","issn-type":"print"},{"key":"4","first-page":"612","article-title":"Maximum flow and minimum-cost flow in almost-linear time","author":"Chen, Li","year":"[2022] \\copyright2022"},{"key":"5","unstructured":"Y. Dong, Y. Gao, R. Peng, I. Razenshteyn, and S. Sawlani, A study of performance of optimal transport, 2020,  arXiv:2005.01182"},{"key":"6","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1016\/0024-3795(89)90490-4","article-title":"On the scaling of multidimensional matrices","volume":"114\/115","author":"Franklin, Joel","year":"1989","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"4","key":"7","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1137\/22M1524254","article-title":"The GenCol algorithm for high-dimensional optimal transport: general formulation and application to barycenters and Wasserstein splines","volume":"5","author":"Friesecke, Gero","year":"2023","journal-title":"SIAM J. Math. Data Sci."},{"issue":"3","key":"8","doi-asserted-by":"publisher","first-page":"A1632--A1654","DOI":"10.1137\/21M140732X","article-title":"Genetic column generation: fast computation of high-dimensional multimarginal optimal transport problems","volume":"44","author":"Friesecke, Gero","year":"2022","journal-title":"SIAM J. Sci. Comput.","ISSN":"http:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"6","key":"9","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1287\/opre.1050.0234","article-title":"Selected topics in column generation","volume":"53","author":"L\u00fcbbecke, Marco E.","year":"2005","journal-title":"Oper. Res.","ISSN":"http:\/\/id.crossref.org\/issn\/0030-364X","issn-type":"print"},{"key":"10","series-title":"Progress in Nonlinear Differential Equations and their Applications","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20828-2","volume-title":"Optimal transport for applied mathematicians","volume":"87","author":"Santambrogio, Filippo","year":"2015","ISBN":"http:\/\/id.crossref.org\/isbn\/9783319208275"},{"key":"11","unstructured":"M. Scetbon, M. Cuturi, and G. Peyr\u00e9, Low-rank Sinkhorn factorization, International Conference on Machine Learning, PMLR, 2021, pp. 9344\u20139354."},{"issue":"3","key":"12","doi-asserted-by":"publisher","first-page":"A1443--A1481","DOI":"10.1137\/16M1106018","article-title":"Stabilized sparse scaling algorithms for entropy regularized transport problems","volume":"41","author":"Schmitzer, Bernhard","year":"2019","journal-title":"SIAM J. Sci. Comput.","ISSN":"http:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"1","key":"13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1137\/22M1478355","article-title":"Low-rank tensor approximations for solving multimarginal optimal transport problems","volume":"16","author":"Str\u00f6ssner, Christoph","year":"2023","journal-title":"SIAM J. Imaging Sci."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2025-94-351\/S0025-5718-2024-03968-6\/mcom3968_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/www.ams.org\/mcom\/2025-94-351\/S0025-5718-2024-03968-6\/S0025-5718-2024-03968-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T17:49:58Z","timestamp":1728582598000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2025-94-351\/S0025-5718-2024-03968-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,26]]},"references-count":13,"journal-issue":{"issue":"351","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["S0025-5718-2024-03968-6"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3968","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["0025-5718","1088-6842"],"issn-type":[{"type":"print","value":"0025-5718"},{"type":"electronic","value":"1088-6842"}],"subject":[],"published":{"date-parts":[[2024,3,26]]}}}