The DOI matches its Crossref record; 52 of the 52 references it cites were found in a registry or an index.
Scaling algorithms for unbalanced optimal transport problems
Open accessAbstract
This article introduces a new class of fast algorithms to approximate variational problems involving unbalanced optimal transport. While classical optimal transport considers only normalized probability distributions, it is important for many applications to be able to compute some sort of relaxed transportation between arbitrary positive measures. A generic class of such “unbalanced” optimal transport problems has been recently proposed by several authors. In this paper, we show how to extend the now classical entropic regularization scheme to these unbalanced problems. This gives rise to fast, highly parallelizable algorithms that operate by performing only diagonal scaling (i.e., pointwise multiplications) of the transportation couplings. They are generalizations of the celebrated Sinkhorn algorithm. We show how these methods can be used to solve unbalanced transport, unbalanced gradient flows, and to compute unbalanced barycenters. We showcase applications to 2-D shape modification, color transfer, and growth models.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Earth Mover's Distance as a Metric for Image Retrieval
Rubner, Y., Tomasi, C., & Guibas, L. J. (2000) · International Journal of Computer Vision · doi:10.1023/a:1026543900054 · Cited by 4,568
Topics in Optimal Transportation
Villani, C. (2003) · Graduate Studies in Mathematics · doi:10.1090/gsm/058 · Cited by 4,412
Villani, C. (2009) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-540-71050-9 · Cited by 3,669
Bregman, L. M. (1967) · USSR Computational Mathematics and Mathematical Physics · doi:10.1016/0041-5553(67)90040-7 · Cited by 2,618
Sinkhorn Distances: Lightspeed Computation of Optimal TransportPreprint
Cuturi, M. (2013) · Cited by 2,385
(2008) · doi:10.1007/978-3-7643-8722-8 · Cited by 2,220
Polar factorization and monotone rearrangement of vector‐valued functions
Brenier, Y. (1991) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.3160440402 · Cited by 1,641
A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
Benamou, J.-D., & Brenier, Y. (2000) · Numerische Mathematik · doi:10.1007/s002110050002 · Cited by 1,609
The Variational Formulation of the Fokker--Planck Equation
Jordan, R., Kinderlehrer, D., & Otto, F. (1998) · SIAM Journal on Mathematical Analysis · doi:10.1137/s0036141096303359 · Cited by 1,603
Deming, W. E., & Stephan, F. F. (1940) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177731829 · Cited by 1,537
THE GEOMETRY OF DISSIPATIVE EVOLUTION EQUATIONS: THE POROUS MEDIUM EQUATION
Otto, F. (2001) · Communications in Partial Differential Equations · doi:10.1081/pde-100002243 · Cited by 1,490
Burkard, R., Dell'Amico, M., & Martello, S. (2009) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898717754 · Cited by 1,394
Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Modeling
Santambrogio, F. (2015) · Progress in Nonlinear Differential Equations and Their Applications · doi:10.1007/978-3-319-20828-2 · Cited by 1,339
A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
Sinkhorn, R. (1964) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177703591 · Cited by 1,032
Barycenters in the Wasserstein Space
Agueh, M., & Carlier, G. (2011) · SIAM Journal on Mathematical Analysis · doi:10.1137/100805741 · Cited by 749
On the Translocation of Masses
Kantorovich, L. V. (2006) · Journal of Mathematical Sciences · doi:10.1007/s10958-006-0049-2 · Cited by 744
Iterative Bregman Projections for Regularized Transportation Problems
Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, L., & Peyré, G. (2015) · SIAM Journal on Scientific Computing · doi:10.1137/141000439 · Cited by 672
Self-citationAn Algorithm for Restricted Least Squares Regression
Dykstra, R. L. (1983) · Journal of the American Statistical Association · doi:10.1080/01621459.1983.10477029 · Cited by 551
Convolutional wasserstein distances: efficient optimal transportation on geometric domains
Solomon, J., de Goes, F., Peyré, G., Cuturi, M., Butscher, A., Nguyen, A., Du, T., & Guibas, L. (2015) · ACM Transactions on Graphics · doi:10.1145/2766963 · Cited by 481
Self-citationFast Computation of Wasserstein Barycenters
Cuturi, M., & Arnaud Doucet, B. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1310.4375 · Cited by 420
On the ergodic convergence rates of a first-order primal–dual algorithm
Chambolle, A., & Pock, T. (2016) · Mathematical Programming · doi:10.1007/s10107-015-0957-3 · Cited by 411
A SURVEY OF THE SCHRÖDINGER PROBLEM AND SOME OF ITS CONNECTIONS WITH OPTIMAL TRANSPORTPreprint
(2016) · Cited by 403
Automated colour grading using colour distribution transfer
Pitié, F., Kokaram, A. C., & Dahyot, R. (2007) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2006.11.011 · Cited by 395
A survey of the Schr\"odinger problem and some of its connections with optimal transportPreprint
Léonard, C. (2013) · arXiv (Cornell University) · Cited by 379
Learning with a Wasserstein Loss
Frogner, C., Zhang, C., Mobahi, H., Araya‐Polo, M., & Poggio, T. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.05439 · Cited by 337
Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
Eckstein, J. (1993) · Mathematics of Operations Research · doi:10.1287/moor.18.1.202 · Cited by 324
Unbalanced optimal transport: Dynamic and Kantorovich formulations
Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F.-X. (2018) · Journal of Functional Analysis · doi:10.1016/j.jfa.2018.03.008 · Cited by 263
Self-citationDisplacement interpolation using Lagrangian mass transport
Bonneel, N., van de Panne, M., Paris, S., et al. (2011) · doi:10.1145/2024156.2024192 · Cited by 241
Beck, A. (2015) · SIAM Journal on Optimization · doi:10.1137/13094829x · Cited by 221
On the scaling of multidimensional matrices
Franklin, J., & Lorenz, J. (1989) · Linear Algebra and its Applications · doi:10.1016/0024-3795(89)90490-4 · Cited by 213
Duality Relationships for Entropy-Like Minimization Problems
Borwein, J. M., & Lewis, A. S. (1991) · SIAM Journal on Control and Optimization · doi:10.1137/0329017 · Cited by 211
Minkowski-Type Theorems and Least-Squares Clustering
Aurenhammer, F., Hoffmann, F., & Aronov, B. (1998) · Algorithmica · doi:10.1007/pl00009187 · Cited by 208
The auction algorithm for the transportation problem
Bertsekas, D. P., & Castanon, D. A. (1989) · Annals of Operations Research · doi:10.1007/bf02216923 · Cited by 183
Optimal Transport with Proximal Splitting
Papadakis, N., Peyré, G., & Oudet, E. (2014) · SIAM Journal on Imaging Sciences · doi:10.1137/130920058 · Cited by 178
Self-citationConvergence of Entropic Schemes for Optimal Transport and Gradient Flows
Carlier, G., Duval, V., Gabriel Peyré, A., & Schmitzer, B. (2017) · SIAM Journal on Mathematical Analysis · doi:10.1137/15m1050264 · Cited by 171
Self-citationDisplacement interpolation using Lagrangian mass transport
Bonneel, N., van de Panne, M., Paris, S., et al. (2011) · ACM Transactions on Graphics · doi:10.1145/2070781.2024192 · Cited by 159
The Optimal Partial Transport Problem
Figalli, A. (2009) · Archive for Rational Mechanics and Analysis · doi:10.1007/s00205-008-0212-7 · Cited by 153
The invisible hand algorithm: Solving the assignment problem with statistical physics
Kosowsky, J. J., & Yuille, A. (1994) · Neural Networks · doi:10.1016/0893-6080(94)90081-7 · Cited by 151
Entropic Approximation of Wasserstein Gradient Flows
Gabriel Peyré, A. (2015) · SIAM Journal on Imaging Sciences · doi:10.1137/15m1010087 · Cited by 117
Total Variation Projection With First Order Schemes
Fadili, J. M., & Gabriel Peyré, A. (2010) · IEEE Transactions on Image Processing · doi:10.1109/tip.2010.2072512 · Cited by 113
A new optimal transport distance on the space of finite Radon measures
Kondratyev, S., Monsaingeon, L., & Vorotnikov, D. (2016) · Advances in Differential Equations · doi:10.57262/ade/1476369298 · Cited by 86
Liero, M., Mielke, A., & Savaré, G. (2015) · doi:10.20347/wias.preprint.2160 · Cited by 86
Wasserstein Propagation for Semi-Supervised Learning
Solomon, J., Rustamov, R. M., Guibas, L. J., & Butscher, A. (2014) · Cited by 84
Liero, M., Mielke, A., & Savaré, G. (2016) · SIAM Journal on Mathematical Analysis · doi:10.1137/15m1041420 · Cited by 78
A Sparse Multiscale Algorithm for Dense Optimal Transport
Schmitzer, B. (2016) · Journal of Mathematical Imaging and Vision · doi:10.1007/s10851-016-0653-9 · Cited by 76
Self-citationAn augmented Lagrangian approach to Wasserstein gradient flows and applications
Benamou, J., Carlier, G., & Laborde, M. (2016) · ESAIM Proceedings and Surveys · doi:10.1051/proc/201654001 · Cited by 76
Kantorovich-Rubinstein norm and its application in the theory of Lipschitz spaces
Hanin, L. G. (1992) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1992-1097344-5 · Cited by 71
Movie and video scale-time equalization application to flicker reduction
Delon, J. (2005) · IEEE Transactions on Image Processing · doi:10.1109/tip.2005.860328 · Cited by 71
Matching with Trade-Offs: Revealed Preferences Over Competing CharacteristicsPreprint
Galichon, A., & Salanié, B. (2009) · SSRN Electronic Journal · doi:10.2139/ssrn.1487307 · Cited by 62
A generalized model for optimal transport of images including dissipation and density modulation
Maas, J., Rumpf, M., Schönlieb, C., & Simon, S. (2015) · ESAIM Mathematical Modelling and Numerical Analysis · doi:10.1051/m2an/2015043 · Cited by 60
A JKO Splitting Scheme for Kantorovich--Fisher--Rao Gradient Flows
Gallouët, T., & Monsaingeon, L. (2017) · SIAM Journal on Mathematical Analysis · doi:10.1137/16m106666x · Cited by 38
A JKO splitting scheme for Kantorovich-Fisher-Rao gradient flowsPreprint
Gallouët, T., & Monsaingeon, L. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.04457 · Cited by 21
Cited by
Schiebinger, G., Shu, J., Tabaka, M., Cleary, B., Subramanian, V., Solomon, A., Gould, J., Liu, S., Lin, S., Berube, P., et al. (2019) · Cell · doi:10.1016/j.cell.2019.01.006 · Cited by 829
Screening cell–cell communication in spatial transcriptomics via collective optimal transport
(2023) · doi:10.1038/s41592-022-01728-4 · Cited by 484
LCDNet: Deep Loop Closure Detection and Point Cloud Registration for LiDAR SLAM
Cattaneo, D., Vaghi, M., & Valada, A. (2022) · IEEE Transactions on Robotics · doi:10.1109/tro.2022.3150683 · Cited by 258
Statistical and machine learning methods for spatially resolved transcriptomics data analysis
Zeng, Z., Li, Y., Li, Y., & Luo, Y. (2022) · Genome Biology · doi:10.1186/s13059-022-02653-7 · Cited by 186
Shekhar, K., Whitney, I. E., Butrus, S., Peng, Y.-R., & Sanes, J. R. (2022) · eLife · doi:10.7554/elife.73809 · Cited by 68
Metadata
- Authors
- Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F.-X.
- Venue
- Mathematics of Computation
- Publisher
- American Mathematical Society (AMS)
- Published
- 2018-02-06
- Volume
- 87
- Issue
- 314
- Pages
- 2563-2609
- ISSN
- 0025-5718 (ISSN-L)
- 1088-6842
- OpenAlex
- W2724892359
- Cited by
- 336
- References
- 52
- FWCI
- 27.48
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
