{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T14:35:28Z","timestamp":1790778928201,"version":"4.1.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,4,15]],"date-time":"2020-04-15T00:00:00Z","timestamp":1586908800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,4,15]],"date-time":"2020-04-15T00:00:00Z","timestamp":1586908800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CCF-1552909"],"award-info":[{"award-number":["CCF-1552909"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CCF-1617851"],"award-info":[{"award-number":["CCF-1617851"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s10107-020-01503-3","type":"journal-article","created":{"date-parts":[[2020,4,15]],"date-time":"2020-04-15T14:02:35Z","timestamp":1586959355000},"page":"395-407","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Better and simpler error analysis of the Sinkhorn\u2013Knopp algorithm for matrix scaling"],"prefix":"10.1007","volume":"188","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,4,15]]},"reference":[{"key":"1503_CR1","doi-asserted-by":"publisher","first-page":"032325","DOI":"10.1103\/PhysRevA.71.032325","volume":"71","author":"S Aaronson","year":"2005","unstructured":"Aaronson, S.: Quantum computing and hidden variables. Phys. Rev. A 71, 032325 (2005)","journal-title":"Phys. Rev. A"},{"key":"1503_CR2","doi-asserted-by":"crossref","unstructured":"Allen Zhu, Z., Li, Y., Oliveira, R., Wigderson, A.: Much faster algorithms for matrix scaling. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS (2017)","DOI":"10.1109\/FOCS.2017.87"},{"key":"1503_CR3","doi-asserted-by":"crossref","unstructured":"Allen Zhu, Z., Orecchia, L.: Using optimization to break the epsilon barrier: a faster and simpler width-independent algorithm for solving positive linear programs in parallel. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1439\u20131456, San Diego, CA, USA (2015)","DOI":"10.1137\/1.9781611973730.95"},{"key":"1503_CR4","unstructured":"Altschuler, J., Weed, J., Rigollet, P.: Near-linear time approximation algorithms for optimal transport via sinkhorn iteration. In: Guyon, I., von Luxburg, U., Bengio, S., Wallach, H.M., Fergus, R., Vishwanathan, S.V.N., Garnett, R. (eds.) Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4\u20139 December 2017, pp. 1961\u20131971, Long Beach, CA, USA (2017)"},{"issue":"3","key":"1503_CR5","doi-asserted-by":"publisher","first-page":"294","DOI":"10.2307\/2525582","volume":"6","author":"M Bacharach","year":"1965","unstructured":"Bacharach, M.: Estimating nonnegative matrices from marginal data. Int. Econ. Rev. 6(3), 294\u2013310 (1965)","journal-title":"Int. Econ. Rev."},{"key":"1503_CR6","doi-asserted-by":"crossref","unstructured":"Balakrishnan, H., Hwang, I., Tomlin, C.J.: Polynomial approximation algorithms for belief matrix maintenance in identity management. In: 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601), vol. 5, pp. 4874\u20134879 (2004)","DOI":"10.1109\/CDC.2004.1429569"},{"key":"1503_CR7","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/0024-3795(89)90489-8","volume":"114","author":"R Bapat","year":"1989","unstructured":"Bapat, R., Raghavan, T.: An extension of a theorem of Darroch and Ratcliff in loglinear models and its application to scaling multidimensional matrices. Linear Algebra Appl. 114, 705\u2013715 (1989). Special Issue Dedicated to Alan J. Hoffman","journal-title":"Linear Algebra Appl."},{"issue":"3","key":"1503_CR8","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/0041-5553(67)90040-7","volume":"7","author":"L Bregman","year":"1967","unstructured":"Bregman, L.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7(3), 200\u2013217 (1967)","journal-title":"USSR Comput. Math. Math. Phys."},{"issue":"1","key":"1503_CR9","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0022-247X(66)90184-3","volume":"16","author":"RA Brualdi","year":"1966","unstructured":"Brualdi, R.A., Parter, S.V., Schneider, H.: The diagonal equivalence of a nonnegative matrix to a stochastic matrix. J. Math. Anal. Appl. 16(1), 31\u201350 (1966)","journal-title":"J. Math. Anal. Appl."},{"key":"1503_CR10","doi-asserted-by":"crossref","unstructured":"Cohen, M.B., Madry, A., Tsipras, D., Vladu, A.: Matrix scaling and balancing via box constrained newton\u2019s method and interior point methods. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS (2017)","DOI":"10.1109\/FOCS.2017.88"},{"issue":"1","key":"1503_CR11","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1214\/aop\/1176996454","volume":"3","author":"I Csiszar","year":"1975","unstructured":"Csiszar, I.: I-divergence geometry of probability distributions and minimization problems. Ann. Probab. 3(1), 146\u2013158 (1975)","journal-title":"Ann. Probab."},{"issue":"3","key":"1503_CR12","doi-asserted-by":"publisher","first-page":"1409","DOI":"10.1214\/aos\/1176347279","volume":"17","author":"I Csiszar","year":"1989","unstructured":"Csiszar, I.: A geometric interpretation of Darroch and Ratcliff\u2019s generalized iterative scaling. Ann. Stat. 17(3), 1409\u20131413 (1989)","journal-title":"Ann. Stat."},{"issue":"4","key":"1503_CR13","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1214\/aoms\/1177731829","volume":"11","author":"WE Deming","year":"1940","unstructured":"Deming, W.E., Stephan, F.F.: On a least squares adjustment of a sampled frequency table when the expected marginal totals are known. Ann. Math. Stat. 11(4), 427\u2013444 (1940)","journal-title":"Ann. Math. Stat."},{"key":"1503_CR14","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, 717\u2013735 (1989). Special Issue Dedicated to Alan J. Hoffman","journal-title":"Linear Algebra Appl."},{"key":"1503_CR15","unstructured":"Gurvits, L., Yianilos, P.N.: The deflation\u2013inflation method for certain semidefinite programming and maximum determinant completion problems. Technical report, NEC Research Institute, 4 Independence Way, Princeton, NJ 08540 (1998)"},{"key":"1503_CR16","unstructured":"Idel, M.: A review of matrix scaling and Sinkhorn\u2019s normal form for matrices and positive maps (2016). ArXiv e-prints. arXiv:1609.06349"},{"issue":"5","key":"1503_CR17","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0167-6377(93)90087-W","volume":"14","author":"B Kalantari","year":"1993","unstructured":"Kalantari, B., Khachiyan, L.: On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms. Oper. Res. Lett. 14(5), 237\u2013244 (1993)","journal-title":"Oper. Res. Lett."},{"key":"1503_CR18","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0024-3795(94)00188-X","volume":"240","author":"B Kalantari","year":"1996","unstructured":"Kalantari, B., Khachiyan, L.: On the complexity of nonnegative-matrix scaling. Linear Algebra Appl. 240, 87\u2013103 (1996)","journal-title":"Linear Algebra Appl."},{"key":"1503_CR19","unstructured":"Kalantari, B., Lari, I., Ricca, F., Simeone, B.: On the complexity of general matrix scaling and entropy minimization via the RAS algorithm. Technical Report, no. 24. Department of Statistics and Applied probability, La Sapienza University, Rome (2002)"},{"issue":"2","key":"1503_CR20","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s10107-006-0021-4","volume":"112","author":"B Kalantari","year":"2008","unstructured":"Kalantari, B., Lari, I., Ricca, F., Simeone, B.: On the complexity of general matrix scaling and entropy minimization via the RAS algorithm. Math. Program. 112(2), 371\u2013401 (2008)","journal-title":"Math. Program."},{"issue":"1","key":"1503_CR21","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":"4","key":"1503_CR22","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s004930070007","volume":"20","author":"N Linial","year":"2000","unstructured":"Linial, N., Samorodnitsky, A., Wigderson, A.: A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica 20(4), 545\u2013568 (2000)","journal-title":"Combinatorica"},{"key":"1503_CR23","doi-asserted-by":"crossref","unstructured":"Luby, M., Nisan, N.: A parallel approximation algorithm for positive linear programming. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC \u201993, pp. 448\u2013457. ACM, New York, NY, USA (1993)","DOI":"10.1145\/167088.167211"},{"issue":"6","key":"1503_CR24","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1068\/a090687","volume":"9","author":"SM Macgill","year":"1977","unstructured":"Macgill, S.M.: Theoretical properties of biproportional matrix adjustments. Environ. Plan. A 9(6), 687\u2013701 (1977)","journal-title":"Environ. Plan. A"},{"key":"1503_CR25","unstructured":"Mahoney, M.W., Rao, S., Wang, D., Zhang, P.: Approximating the solution to mixed packing and covering LPs in parallel $$O(\\epsilon ^{-3})$$ time. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11\u201315, 2016, pp. 52:1\u201352:14, Rome, Italy (2016)"},{"issue":"2","key":"1503_CR26","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1090\/S0002-9939-1967-0215873-6","volume":"18","author":"M Menon","year":"1967","unstructured":"Menon, M.: Reduction of a matrix with positive elements to a doubly stochastic matrix. Proc. Am. Math. Soc. 18(2), 244\u2013247 (1967)","journal-title":"Proc. Am. Math. Soc."},{"key":"1503_CR27","doi-asserted-by":"publisher","DOI":"10.1002\/9781119993308","volume-title":"Modelling Transport","author":"J\u00a0d\u00a0D Ort\u00fazar","year":"2011","unstructured":"Ort\u00fazar, J\u00a0d\u00a0D, Willumsen, L\u00a0.G.: Modelling Transport. Wiley, New York (2011)"},{"key":"1503_CR28","series-title":"Cambridge Series in Statistical and Probabilistic Mathematics","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511811555","volume-title":"A User\u2019s Guide to Measure Theoretic Probability","author":"D Pollard","year":"2001","unstructured":"Pollard, D.: A User\u2019s Guide to Measure Theoretic Probability. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2001)"},{"key":"1503_CR29","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0024-3795(84)90101-0","volume":"62","author":"T Raghavan","year":"1984","unstructured":"Raghavan, T.: On pairs of multidimensional matrices. Linear Algebra Appl. 62, 263\u2013268 (1984)","journal-title":"Linear Algebra Appl."},{"key":"1503_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9620-8","volume-title":"Approximate Distributions of Order Statistics","author":"R-D Reiss","year":"1989","unstructured":"Reiss, R.-D.: Approximate Distributions of Order Statistics. Springer, Berlin (1989)"},{"key":"1503_CR31","unstructured":"Rote, G., Zachariasen, M.: Matrix scaling by network flow. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201907, pp. 848\u2013854. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2007)"},{"key":"1503_CR32","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1016\/0024-3795(89)90491-6","volume":"114","author":"U Rothblum","year":"1989","unstructured":"Rothblum, U., Schneider, H.: Scalings of matrices which have prespecified row sums and column sums via optimization. Linear Algebra Appl. 114, 737\u2013764 (1989). (Special Issue Dedicated to Alan J. Hoffman)","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"1503_CR33","doi-asserted-by":"publisher","first-page":"1160","DOI":"10.1214\/aos\/1176324703","volume":"23","author":"L Ruschendorf","year":"1995","unstructured":"Ruschendorf, L.: Convergence of the iterative proportional fitting procedure. Ann. Stat. 23(4), 1160\u20131174 (1995)","journal-title":"Ann. Stat."},{"key":"1503_CR34","doi-asserted-by":"crossref","unstructured":"Sason, I., Verd\u00fa, S.: Upper bounds on the relative entropy and R\u00e9nyi divergence as a function of total variation distance for finite alphabets. In: 2015 IEEE Information Theory Workshop\u2014Fall (ITW), Jeju Island, South Korea, October 11\u201315, 2015, pp. 214\u2013218. IEEE (2015)","DOI":"10.1109\/ITWF.2015.7360766"},{"key":"1503_CR35","unstructured":"Schr\u00f6dinger, E.: \u00dcber die umkehrung der naturgesetze. Preuss. Akad. Wiss., Phys.-Math. Kl, pp. 412\u2013422 (1931)"},{"issue":"4","key":"1503_CR36","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. Mon. 74(4), 402\u2013405 (1967)","journal-title":"Am. Math. Mon."},{"issue":"2","key":"1503_CR37","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(2), 343\u2013348 (1967)","journal-title":"Pac. J. Math."},{"key":"1503_CR38","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0024-3795(91)90157-R","volume":"150","author":"GW Soules","year":"1991","unstructured":"Soules, G.W.: The rate of convergence of Sinkhorn balancing. Linear Algebra Appl. 150, 3\u201340 (1991)","journal-title":"Linear Algebra Appl."},{"key":"1503_CR39","unstructured":"Xi\u2019an: Statistics stack exchange. https:\/\/stats.stackexchange.com\/questions\/130432\/differences-between-bhattacharyya-distance-and-kl-divergence (2014). Accessed 15 Jan 2018"},{"key":"1503_CR40","doi-asserted-by":"crossref","unstructured":"Young, N.E.: Sequential and parallel algorithms for mixed packing and covering. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS, pp. 538\u2013546, Las Vegas, Nevada, USA (2001)","DOI":"10.1109\/SFCS.2001.959930"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01503-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01503-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01503-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,22]],"date-time":"2021-06-22T15:51:57Z","timestamp":1624377117000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01503-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,15]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["1503"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01503-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,15]]},"assertion":[{"value":"17 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}