{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T08:18:07Z","timestamp":1766391487026,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,12,14]],"date-time":"2021-12-14T00:00:00Z","timestamp":1639440000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,14]],"date-time":"2021-12-14T00:00:00Z","timestamp":1639440000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100013296","name":"Max Planck Institute for Mathematics in the Sciences","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100013296","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We derive an a priori parameter range for overrelaxation of the Sinkhorn algorithm, which guarantees global convergence and a strictly faster asymptotic local convergence. Guided by the spectral analysis of the linearized problem we pursue a zero cost procedure to choose a near optimal relaxation parameter.<\/jats:p>","DOI":"10.1007\/s11590-021-01830-0","type":"journal-article","created":{"date-parts":[[2021,12,14]],"date-time":"2021-12-14T16:19:49Z","timestamp":1639498789000},"page":"2209-2220","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A note on overrelaxation in the Sinkhorn algorithm"],"prefix":"10.1007","volume":"16","author":[{"given":"Tobias","family":"Lehmann","sequence":"first","affiliation":[]},{"given":"Max-K.","family":"von Renesse","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Sambale","sequence":"additional","affiliation":[]},{"given":"Andr\u00e9","family":"Uschmajew","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,12,14]]},"reference":[{"key":"1830_CR1","unstructured":"Cuturi, M.: Sinkhorn distances: lightspeed computation of optimal transport. In: Burges, C.J.C., et al. (eds.) Advances in Neural Information Processing Systems, vol. 26. Curran Associates, Inc., pp. 2292\u20132300 (2013)"},{"key":"1830_CR2","doi-asserted-by":"publisher","first-page":"402","DOI":"10.2307\/2314570","volume":"74","author":"R Sinkhorn","year":"1967","unstructured":"Sinkhorn, R.: Diagonal equivalence to matrices with prescribed row and column sums. Am. Math. Monthly 74, 402\u2013405 (1967)","journal-title":"Am. Math. Monthly"},{"issue":"115","key":"1830_CR3","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1016\/0024-3795(89)90490-4","volume":"114","author":"J Franklin","year":"1989","unstructured":"Franklin, J., Lorenz, J.: On the scaling of multidimensional matrices. Linear Algebra Appl. 114(115), 717\u2013735 (1989)","journal-title":"Linear Algebra Appl."},{"issue":"5\u20136","key":"1830_CR4","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1561\/2200000073","volume":"11","author":"G Peyr\u00e9","year":"2019","unstructured":"Peyr\u00e9, G., Cuturi, M.: Computational optimal transport. Found. Trends Mach. Learn. 11(5\u20136), 355\u2013607 (2019)","journal-title":"Found. Trends Mach. Learn."},{"issue":"5","key":"1830_CR5","doi-asserted-by":"publisher","first-page":"143","DOI":"10.3390\/a14050143","volume":"14","author":"A Thibault","year":"2021","unstructured":"Thibault, A., Chizat, L., Dossal, C., Papadakis, N.: Overrelaxed Sinkhorn\u2013Knopp algorithm for regularized optimal transport. Algorithms 14(5), 143 (2021)","journal-title":"Algorithms"},{"issue":"6","key":"1830_CR6","doi-asserted-by":"publisher","first-page":"1079","DOI":"10.1017\/S0956792517000274","volume":"30","author":"G Peyr\u00e9","year":"2019","unstructured":"Peyr\u00e9, G., Chizat, L., Vialard, F.-X., Solomon, J.: Quantum entropic regularization of matrix-valued optimal transport. Eur. J. Appl. Math. 30(6), 1079\u20131102 (2019)","journal-title":"Eur. J. Appl. Math."},{"issue":"4","key":"1830_CR7","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1002\/cpa.21437","volume":"66","author":"C Cotar","year":"2013","unstructured":"Cotar, C., Friesecke, G., Kl\u00fcppelberg, C.: Density functional theory and optimal transportation with Coulomb cost. Commun. Pure Appl. Math. 66(4), 548\u2013599 (2013)","journal-title":"Commun. Pure Appl. Math."},{"issue":"1","key":"1830_CR8","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1137\/060659624","volume":"30","author":"PA Knight","year":"2008","unstructured":"Knight, P.A.: The Sinkhorn\u2013Knopp algorithm: convergence and applications. SIAM J. Matrix Anal. Appl. 30(1), 261\u2013275 (2008)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"3","key":"1830_CR9","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1093\/imanum\/drs019","volume":"33","author":"PA Knight","year":"2013","unstructured":"Knight, P.A., Ruiz, D.: A fast algorithm for matrix balancing. IMA J. Numer. Anal. 33(3), 1029\u20131047 (2013)","journal-title":"IMA J. Numer. Anal."},{"key":"1830_CR10","unstructured":"Brauer, C., Clason, C., Lorenz, D., Wirth, B.: A Sinkhorn\u2013Newton method for entropic optimal transport. arXiv:1710.06635 (2017)"},{"key":"1830_CR11","doi-asserted-by":"crossref","DOI":"10.1002\/9781119003144","volume-title":"Modeling and Analysis of Compositional Data","author":"V Pawlowsky-Glahn","year":"2015","unstructured":"Pawlowsky-Glahn, V., Egozcue, J.J., Tolosana-Delgado, R.: Modeling and Analysis of Compositional Data. Wiley, Chichester (2015)"},{"key":"1830_CR12","doi-asserted-by":"publisher","first-page":"343","DOI":"10.2140\/pjm.1967.21.343","volume":"21","author":"R Sinkhorn","year":"1967","unstructured":"Sinkhorn, R., Knopp, P.: Concerning nonnegative matrices and doubly stochastic matrices. Pac. J. Math. 21, 343\u2013348 (1967)","journal-title":"Pac. J. Math."},{"issue":"4","key":"1830_CR13","doi-asserted-by":"publisher","first-page":"57","DOI":"10.17713\/ajs.v45i4.142","volume":"45","author":"C Barcelo-Vidal","year":"2016","unstructured":"Barcelo-Vidal, C., Martin-Fernandez, J.-A.: The mathematics of compositional analysis. Aust. J. Stat. 45(4), 57\u201371 (2016)","journal-title":"Aust. J. Stat."},{"issue":"1","key":"1830_CR14","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1017\/S0305004100072911","volume":"117","author":"SP Eveson","year":"1995","unstructured":"Eveson, S.P., Nussbaum, R.D.: An elementary proof of the Birkhoff\u2013Hopf theorem. Math. Proc. Cambridge Philos. Soc. 117(1), 31\u201355 (1995)","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"1830_CR15","volume-title":"Iterative Solution of Large Linear Systems","author":"DM Young","year":"1971","unstructured":"Young, D.M.: Iterative Solution of Large Linear Systems. Academic Press, New York (1971)"},{"key":"1830_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-28483-5","volume-title":"Iterative Solution of Large Sparse Systems of Equations","author":"W Hackbusch","year":"2016","unstructured":"Hackbusch, W.: Iterative Solution of Large Sparse Systems of Equations, 2nd edn. Springer, Cham (2016)","edition":"2"},{"issue":"3","key":"1830_CR17","doi-asserted-by":"publisher","first-page":"1853","DOI":"10.1137\/130929886","volume":"7","author":"S Ferradans","year":"2014","unstructured":"Ferradans, S., Papadakis, N., Peyr\u00e9, G., Aujol, J.-F.: Regularized discrete optimal transport. SIAM J. Imaging Sci. 7(3), 1853\u20131882 (2014)","journal-title":"SIAM J. Imaging Sci."},{"issue":"78","key":"1830_CR18","first-page":"1","volume":"22","author":"R Flamary","year":"2021","unstructured":"Flamary, R., et al.: POT: python optimal transport. J. Mach. Learn. Res. 22(78), 1\u20138 (2021)","journal-title":"J. Mach. Learn. Res."},{"key":"1830_CR19","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1137\/0712026","volume":"12","author":"LA Hageman","year":"1975","unstructured":"Hageman, L.A., Porsching, T.A.: Aspects of nonlinear block successive overrelaxation. SIAM J. Numer. Anal. 12, 316\u2013335 (1975)","journal-title":"SIAM J. Numer. Anal."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01830-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-021-01830-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01830-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T03:26:40Z","timestamp":1699932400000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-021-01830-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,14]]},"references-count":19,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1830"],"URL":"https:\/\/doi.org\/10.1007\/s11590-021-01830-0","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2021,12,14]]},"assertion":[{"value":"20 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 December 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}