Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the success of MOT is severely limited by a lack of efficient algorithms. Indeed, MOT in general requires exponential time in the number of marginals
 Home
 Search Results
 Page 1 of 1
Search for: All records

Total Resources2
 Resource Type

00000020000
 More
 Availability

20
 Author / Contributor
 Filter by Author / Creator


Altschuler, Jason M. (2)

BoixAdserà, Enric (1)

NilesWeed, Jonathan (1)

Stromme, Austin J. (1)

#Tyler Phillips, Kenneth E. (0)

#Willis, Ciara (0)

& AbreuRamos, E. D. (0)

& Abramson, C. I. (0)

& AbreuRamos, E. D. (0)

& Adams, S.G. (0)

& Ahmed, K. (0)

& Ahmed, Khadija. (0)

& Aina, D.K. Jr. (0)

& AkcilOkan, O. (0)

& Akuom, D. (0)

& Aleven, V. (0)

& AndrewsLarson, C. (0)

& Archibald, J. (0)

& Arnett, N. (0)

& Arya, G. (0)

 Filter by Editor


& Spizer, S. M. (0)

& . Spizer, S. (0)

& Ahn, J. (0)

& Bateiha, S. (0)

& Bosch, N. (0)

& Brennan K. (0)

& Brennan, K. (0)

& Chen, B. (0)

& Chen, Bodong (0)

& Drown, S. (0)

& Ferretti, F. (0)

& Higgins, A. (0)

& J. Peters (0)

& Kali, Y. (0)

& RuizArias, P.M. (0)

& S. Spitzer (0)

& Sahin. I. (0)

& Spitzer, S. (0)

& Spitzer, S.M. (0)

(submitted  in Review for IEEE ICASSP2024) (0)


Have feedback or suggestions for a way to improve these results?
!
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Abstract k and their support sizesn . This paper develops a general theory about what “structure” makes MOT solvable in time. We develop a unified algorithmic framework for solving MOT in$$\mathrm {poly}(n,k)$$ $\mathrm{poly}(n,k)$ time by characterizing the structure that different algorithms require in terms of simple variants of the dual feasibility oracle. This framework has several benefits. First, it enables us to show that the Sinkhorn algorithm, which is currently the most popular MOT algorithm, requires strictly more structure than other algorithms do to solve MOT in$$\mathrm {poly}(n,k)$$ $\mathrm{poly}(n,k)$ time. Second, our framework makes it much simpler to develop$$\mathrm {poly}(n,k)$$ $\mathrm{poly}(n,k)$ time algorithms for a given MOT problem. In particular, it is necessary and sufficient to (approximately) solve the dual feasibility oracle—which is much more amenable to standard algorithmic techniques. We illustrate this easeofuse by developing$$\mathrm {poly}(n,k)$$ $\mathrm{poly}(n,k)$ time algorithms for three general classes of MOT cost structures: (1) graphical structure; (2) setoptimization structure; and (3) lowrank plus sparse structure. For structure (1), we recover the known result that Sinkhorn has$$\mathrm {poly}(n,k)$$ $\mathrm{poly}(n,k)$ runtime; moreover, we provide the first$$\mathrm {poly}(n,k)$$ $\mathrm{poly}(n,k)$ time algorithms for computing solutions that are exact and sparse. For structures (2)(3), we give the first$$\mathrm {poly}(n,k)$$ $\mathrm{poly}(n,k)$ time algorithms, even for approximate computation. Together, these three structures encompass many—if not most—current applications of MOT.$$\mathrm {poly}(n,k)$$ $\mathrm{poly}(n,k)$ 
Altschuler, Jason M. ; NilesWeed, Jonathan ; Stromme, Austin J. ( , SIAM Journal on Mathematical Analysis)