Accelerating the Sinkhorn Algorithm for Sparse Multi-Marginal Optimal Transport via Fast Fourier Transforms

We consider the numerical solution of the discrete multi-marginal optimal transport (MOT) by means of the Sinkhorn algorithm. In general, the Sinkhorn algorithm suffers from the curse of dimensionality with respect to the number of marginals. If the MOT cost function decouples according to a tree or...

Full description

Saved in:
Bibliographic Details
Published in:Algorithms 2022-09, Vol.15 (9), p.311
Main Authors: Ba, Fatima Antarou, Quellmalz, Michael
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Complexity
Cost function
Entropy
fast Fourier transform
Fast Fourier transformations
image processing
Mathematical analysis
multi-marginal optimal transport
optimal transport
Optimization
Probability
Sinkhorn algorithm
Sparsity
Wasserstein barycenter
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c397t-135315b78aed9c4da2a3992d777da8c2614aa8aec8f2115b860a6000268333ef3
cites cdi_FETCH-LOGICAL-c397t-135315b78aed9c4da2a3992d777da8c2614aa8aec8f2115b860a6000268333ef3
container_end_page
container_issue 9
container_start_page 311
container_title Algorithms
container_volume 15
creator Ba, Fatima Antarou
Quellmalz, Michael
description We consider the numerical solution of the discrete multi-marginal optimal transport (MOT) by means of the Sinkhorn algorithm. In general, the Sinkhorn algorithm suffers from the curse of dimensionality with respect to the number of marginals. If the MOT cost function decouples according to a tree or circle, its complexity is linear in the number of marginal measures. In this case, we speed up the convolution with the radial kernel required in the Sinkhorn algorithm via non-uniform fast Fourier methods. Each step of the proposed accelerated Sinkhorn algorithm with a tree-structured cost function has a complexity of O(KN) instead of the classical O(KN2) for straightforward matrix–vector operations, where K is the number of marginals and each marginal measure is supported on, at most, N points. In the case of a circle-structured cost function, the complexity improves from O(KN3) to O(KN2). This is confirmed through numerical experiments.
doi_str_mv 10.3390/a15090311
format article
fullrecord <record><control><sourceid>gale_doaj_</sourceid><recordid>TN_cdi_doaj_primary_oai_doaj_org_article_9345f6ac0c3f40c9b17a755bb78c6f87</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><galeid>A745142951</galeid><doaj_id>oai_doaj_org_article_9345f6ac0c3f40c9b17a755bb78c6f87</doaj_id><sourcerecordid>A745142951</sourcerecordid><originalsourceid>FETCH-LOGICAL-c397t-135315b78aed9c4da2a3992d777da8c2614aa8aec8f2115b860a6000268333ef3</originalsourceid><addsrcrecordid>eNpNkcFO5DAMhivESgssh32DSJz2UEiaJmmOI8SwSCAOwDnypEknQ6fpOhkk3p7sdoWQD7bs359tuap-MnrJuaZXwATVlDN2VJ0wrXXddpoff4m_V6cp7SiVQkt2Ur2urHWjQ8hhGkjeOvIUptdtxImsxiFiyNs98RHJ0wyYHHk4jDnUD4BDmGAkj3MO--KfEaY0R8zkLQBZQ8pkHQ8YHC6lQtinH9U3D2Ny5__9WfWyvnm-_l3fP97eXa_ua8u1yjXjgjOxUR24Xtu2hwa41k2vlOqhs41kLUAp2s43rAg7SUFSShvZcc6d52fV3cLtI-zMjGVDfDcRgvmXiDgYwBzs6IzmrfASLLXct9TqDVOghNiU6Vb6ThXWxcKaMf45uJTNrtxVTk-mUUy2SgrJi-pyUQ1QoGHyMSPYYr3bBxsn50PJr1QrWNtowUrDr6XBYkwJnf9ck1Hz95Hm85H8A4Kkj10</addsrcrecordid><sourcetype>Open Website</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2716476563</pqid></control><display><type>article</type><title>Accelerating the Sinkhorn Algorithm for Sparse Multi-Marginal Optimal Transport via Fast Fourier Transforms</title><source>Publicly Available Content Database (Proquest) (PQ_SDU_P3)</source><creator>Ba, Fatima Antarou ; Quellmalz, Michael</creator><creatorcontrib>Ba, Fatima Antarou ; Quellmalz, Michael</creatorcontrib><description>We consider the numerical solution of the discrete multi-marginal optimal transport (MOT) by means of the Sinkhorn algorithm. In general, the Sinkhorn algorithm suffers from the curse of dimensionality with respect to the number of marginals. If the MOT cost function decouples according to a tree or circle, its complexity is linear in the number of marginal measures. In this case, we speed up the convolution with the radial kernel required in the Sinkhorn algorithm via non-uniform fast Fourier methods. Each step of the proposed accelerated Sinkhorn algorithm with a tree-structured cost function has a complexity of O(KN) instead of the classical O(KN2) for straightforward matrix–vector operations, where K is the number of marginals and each marginal measure is supported on, at most, N points. In the case of a circle-structured cost function, the complexity improves from O(KN3) to O(KN2). This is confirmed through numerical experiments.</description><identifier>ISSN: 1999-4893</identifier><identifier>EISSN: 1999-4893</identifier><identifier>DOI: 10.3390/a15090311</identifier><language>eng</language><publisher>Basel: MDPI AG</publisher><subject>Algorithms ; Approximation ; Complexity ; Cost function ; Entropy ; fast Fourier transform ; Fast Fourier transformations ; image processing ; Mathematical analysis ; multi-marginal optimal transport ; optimal transport ; Optimization ; Probability ; Sinkhorn algorithm ; Sparsity ; Wasserstein barycenter</subject><ispartof>Algorithms, 2022-09, Vol.15 (9), p.311</ispartof><rights>COPYRIGHT 2022 MDPI AG</rights><rights>2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c397t-135315b78aed9c4da2a3992d777da8c2614aa8aec8f2115b860a6000268333ef3</citedby><cites>FETCH-LOGICAL-c397t-135315b78aed9c4da2a3992d777da8c2614aa8aec8f2115b860a6000268333ef3</cites><orcidid>0000-0002-9710-9744 ; 0000-0001-6206-5705</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/2716476563/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$Hfree_for_read</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/2716476563?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>314,780,784,25753,27924,27925,37012,44590,75126</link.rule.ids></links><search><creatorcontrib>Ba, Fatima Antarou</creatorcontrib><creatorcontrib>Quellmalz, Michael</creatorcontrib><title>Accelerating the Sinkhorn Algorithm for Sparse Multi-Marginal Optimal Transport via Fast Fourier Transforms</title><title>Algorithms</title><description>We consider the numerical solution of the discrete multi-marginal optimal transport (MOT) by means of the Sinkhorn algorithm. In general, the Sinkhorn algorithm suffers from the curse of dimensionality with respect to the number of marginals. If the MOT cost function decouples according to a tree or circle, its complexity is linear in the number of marginal measures. In this case, we speed up the convolution with the radial kernel required in the Sinkhorn algorithm via non-uniform fast Fourier methods. Each step of the proposed accelerated Sinkhorn algorithm with a tree-structured cost function has a complexity of O(KN) instead of the classical O(KN2) for straightforward matrix–vector operations, where K is the number of marginals and each marginal measure is supported on, at most, N points. In the case of a circle-structured cost function, the complexity improves from O(KN3) to O(KN2). This is confirmed through numerical experiments.</description><subject>Algorithms</subject><subject>Approximation</subject><subject>Complexity</subject><subject>Cost function</subject><subject>Entropy</subject><subject>fast Fourier transform</subject><subject>Fast Fourier transformations</subject><subject>image processing</subject><subject>Mathematical analysis</subject><subject>multi-marginal optimal transport</subject><subject>optimal transport</subject><subject>Optimization</subject><subject>Probability</subject><subject>Sinkhorn algorithm</subject><subject>Sparsity</subject><subject>Wasserstein barycenter</subject><issn>1999-4893</issn><issn>1999-4893</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2022</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><sourceid>DOA</sourceid><recordid>eNpNkcFO5DAMhivESgssh32DSJz2UEiaJmmOI8SwSCAOwDnypEknQ6fpOhkk3p7sdoWQD7bs359tuap-MnrJuaZXwATVlDN2VJ0wrXXddpoff4m_V6cp7SiVQkt2Ur2urHWjQ8hhGkjeOvIUptdtxImsxiFiyNs98RHJ0wyYHHk4jDnUD4BDmGAkj3MO--KfEaY0R8zkLQBZQ8pkHQ8YHC6lQtinH9U3D2Ny5__9WfWyvnm-_l3fP97eXa_ua8u1yjXjgjOxUR24Xtu2hwa41k2vlOqhs41kLUAp2s43rAg7SUFSShvZcc6d52fV3cLtI-zMjGVDfDcRgvmXiDgYwBzs6IzmrfASLLXct9TqDVOghNiU6Vb6ThXWxcKaMf45uJTNrtxVTk-mUUy2SgrJi-pyUQ1QoGHyMSPYYr3bBxsn50PJr1QrWNtowUrDr6XBYkwJnf9ck1Hz95Hm85H8A4Kkj10</recordid><startdate>20220901</startdate><enddate>20220901</enddate><creator>Ba, Fatima Antarou</creator><creator>Quellmalz, Michael</creator><general>MDPI AG</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7TB</scope><scope>7XB</scope><scope>8AL</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FR3</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K7-</scope><scope>KR7</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0N</scope><scope>M7S</scope><scope>P62</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope><scope>Q9U</scope><scope>DOA</scope><orcidid>https://orcid.org/0000-0002-9710-9744</orcidid><orcidid>https://orcid.org/0000-0001-6206-5705</orcidid></search><sort><creationdate>20220901</creationdate><title>Accelerating the Sinkhorn Algorithm for Sparse Multi-Marginal Optimal Transport via Fast Fourier Transforms</title><author>Ba, Fatima Antarou ; Quellmalz, Michael</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c397t-135315b78aed9c4da2a3992d777da8c2614aa8aec8f2115b860a6000268333ef3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2022</creationdate><topic>Algorithms</topic><topic>Approximation</topic><topic>Complexity</topic><topic>Cost function</topic><topic>Entropy</topic><topic>fast Fourier transform</topic><topic>Fast Fourier transformations</topic><topic>image processing</topic><topic>Mathematical analysis</topic><topic>multi-marginal optimal transport</topic><topic>optimal transport</topic><topic>Optimization</topic><topic>Probability</topic><topic>Sinkhorn algorithm</topic><topic>Sparsity</topic><topic>Wasserstein barycenter</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Ba, Fatima Antarou</creatorcontrib><creatorcontrib>Quellmalz, Michael</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical &amp; Transportation Engineering Abstracts</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>Computing Database (Alumni Edition)</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Database‎ (1962 - current)</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Engineering Research Database</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer Science Database</collection><collection>Civil Engineering Abstracts</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>Computing Database</collection><collection>Engineering Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>Publicly Available Content Database (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering Collection</collection><collection>ProQuest Central Basic</collection><collection>Directory of Open Access Journals</collection><jtitle>Algorithms</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Ba, Fatima Antarou</au><au>Quellmalz, Michael</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Accelerating the Sinkhorn Algorithm for Sparse Multi-Marginal Optimal Transport via Fast Fourier Transforms</atitle><jtitle>Algorithms</jtitle><date>2022-09-01</date><risdate>2022</risdate><volume>15</volume><issue>9</issue><spage>311</spage><pages>311-</pages><issn>1999-4893</issn><eissn>1999-4893</eissn><abstract>We consider the numerical solution of the discrete multi-marginal optimal transport (MOT) by means of the Sinkhorn algorithm. In general, the Sinkhorn algorithm suffers from the curse of dimensionality with respect to the number of marginals. If the MOT cost function decouples according to a tree or circle, its complexity is linear in the number of marginal measures. In this case, we speed up the convolution with the radial kernel required in the Sinkhorn algorithm via non-uniform fast Fourier methods. Each step of the proposed accelerated Sinkhorn algorithm with a tree-structured cost function has a complexity of O(KN) instead of the classical O(KN2) for straightforward matrix–vector operations, where K is the number of marginals and each marginal measure is supported on, at most, N points. In the case of a circle-structured cost function, the complexity improves from O(KN3) to O(KN2). This is confirmed through numerical experiments.</abstract><cop>Basel</cop><pub>MDPI AG</pub><doi>10.3390/a15090311</doi><orcidid>https://orcid.org/0000-0002-9710-9744</orcidid><orcidid>https://orcid.org/0000-0001-6206-5705</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1999-4893
ispartof Algorithms, 2022-09, Vol.15 (9), p.311
issn 1999-4893
1999-4893
language eng
recordid cdi_doaj_primary_oai_doaj_org_article_9345f6ac0c3f40c9b17a755bb78c6f87
source Publicly Available Content Database (Proquest) (PQ_SDU_P3)
subjects Algorithms
Approximation
Complexity
Cost function
Entropy
fast Fourier transform
Fast Fourier transformations
image processing
Mathematical analysis
multi-marginal optimal transport
optimal transport
Optimization
Probability
Sinkhorn algorithm
Sparsity
Wasserstein barycenter
title Accelerating the Sinkhorn Algorithm for Sparse Multi-Marginal Optimal Transport via Fast Fourier Transforms
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T11%3A55%3A25IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-gale_doaj_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Accelerating%20the%20Sinkhorn%20Algorithm%20for%20Sparse%20Multi-Marginal%20Optimal%20Transport%20via%20Fast%20Fourier%20Transforms&rft.jtitle=Algorithms&rft.au=Ba,%20Fatima%20Antarou&rft.date=2022-09-01&rft.volume=15&rft.issue=9&rft.spage=311&rft.pages=311-&rft.issn=1999-4893&rft.eissn=1999-4893&rft_id=info:doi/10.3390/a15090311&rft_dat=%3Cgale_doaj_%3EA745142951%3C/gale_doaj_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c397t-135315b78aed9c4da2a3992d777da8c2614aa8aec8f2115b860a6000268333ef3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2716476563&rft_id=info:pmid/&rft_galeid=A745142951&rfr_iscdi=true