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

dc.contributor.authorBa, Fatima Antarou
dc.contributor.authorQuellmalz, Michael
dc.date.accessioned2022-10-05T12:22:29Z
dc.date.available2022-10-05T12:22:29Z
dc.date.issued2022-08-30
dc.date.updated2022-09-23T14:48:31Z
dc.description.abstractWe 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.
dc.description.sponsorshipDFG, 495365311, Bewegungsdetektion in der optischen Diffraktionstomographie und der dynamischen Einzelmolekülmikropkopie
dc.description.sponsorshipTU Berlin, Open-Access-Mittel – 2022
dc.identifier.eissn1999-4893
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/17547
dc.identifier.urihttps://doi.org/10.14279/depositonce-16328
dc.language.isoen
dc.rightsLicensee 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/).
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subject.ddc510 Mathematikde
dc.subject.othermulti-marginal optimal transporten
dc.subject.otherSinkhorn algorithmen
dc.subject.otherfast Fourier transformen
dc.subject.otherimage processingen
dc.subject.otheroptimal transporten
dc.subject.otherWasserstein barycenteren
dc.titleAccelerating the Sinkhorn Algorithm for Sparse Multi-Marginal Optimal Transport via Fast Fourier Transforms
dc.typeArticle
dc.type.versionpublishedVersion
dcterms.bibliographicCitation.articlenumber311
dcterms.bibliographicCitation.doi10.3390/a15090311
dcterms.bibliographicCitation.issue9
dcterms.bibliographicCitation.journaltitleAlgorithms
dcterms.bibliographicCitation.originalpublishernameMDPI
dcterms.bibliographicCitation.originalpublisherplaceBasel
dcterms.bibliographicCitation.volume15
tub.accessrights.dnbfree
tub.affiliationTechnische Universität Berlin::Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik::FG Angewandte Mathematik
tub.publisher.universityorinstitutionTechnische Universität Berlin
Files
Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
algorithms-15-00311-v2.pdf
Size:
1.25 MB
Format:
Adobe Portable Document Format
Description:
Collections