{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:36Z","timestamp":1787340396401,"version":"build-2736575974"},"reference-count":64,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["2950-120715"],"award-info":[{"award-number":["2950-120715"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["2950-120719"],"award-info":[{"award-number":["2950-120719"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We present a spectral analysis of a continuous scaling algorithm for matrix scaling and operator scaling. The main result is that if the input matrix or operator has a spectral gap, then a natural gradient flow has linear convergence. This implies that a simple gradient descent algorithm also has linear convergence under the same assumption. The spectral gap condition for operator scaling is closely related to the notion of quantum expander studied in quantum information theory. The spectral analysis also provides bounds on some important quantities of the scaling problems, such as the condition number of the scaling solution and the capacity of the matrix and operator. These results can be used in various applications of scaling problems, including matrix scaling on expander graphs, permanent lower bounds on random matrices, the Paulsen problem on random frames, and Brascamp--Lieb constants on random operators. In some applications, the inputs of interest satisfy the spectral condition and we prove significantly stronger bounds than the worst case bounds.<\/jats:p>","DOI":"10.1137\/20m1315981","type":"journal-article","created":{"date-parts":[[2021,6,22]],"date-time":"2021-06-22T12:09:52Z","timestamp":1624363792000},"page":"1034-1102","source":"Crossref","is-referenced-by-count":2,"title":["Spectral Analysis of Matrix Scaling and Operator Scaling"],"prefix":"10.1137","volume":"50","author":[{"given":"Tsz Chiu","family":"Kwok","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lap Chi","family":"Lau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Akshay","family":"Ramachandran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,6,22]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"Z. Allen-Zhu, A. Garg, Y. Li, R. Oliveira, and A. Wigderson,\n                      Operator scaling via geodescially convex optimization, invariant theory and polynomial identity testing\n                      , in Proceeedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), 2018, pp. 172-181.","DOI":"10.1145\/3188745.3188942"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"Z. Allen-Zhu, Y. Li, R. Oliveira, and A. Wigderson,\n                      Much faster algorithms for matrix scaling\n                      , in Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2017.","DOI":"10.1109\/FOCS.2017.87"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/14.1.1"},{"key":"atypb4","first-page":"251","author":"Ball K.","year":"1989","journal-title":"Berlin"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s002220050267"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000435"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a003"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-007-0619-6"},{"key":"atypb9","unstructured":"R. Bhatia,\n                      Positive Definite Matrices\n                      , Princeton University Press, Princeton, NJ, 2007."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(76)90184-5"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"P. Buergisser, C. Franks, A. Garg, R. Oliveira, M. Walter, and A. Wigderson,\n                      Efficient algorithms for tensor scaling, quantum marginals and moment polytopes\n                      , in Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2018.","DOI":"10.1109\/FOCS.2018.00088"},{"key":"atypb12","first-page":"845","author":"Buergisser P.","year":"2019","journal-title":"Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(75)90075-0"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"M. B. Cohen, A. Madry, D. Tsipras, and A. Vladu,\n                      Matrix scaling and balancing via box constrained Newton's method and interior point methods\n                      , in Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2017.","DOI":"10.1109\/FOCS.2017.88"},{"key":"atypb15","unstructured":"M. Cuturi,\n                      Sinkhorn distances: Lightspeed computation of optimal transport\n                      , in Proceedings of the 26th International Conference on Neural Information Processing Systems (NIPS), 2013, pp. 2292-2300."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(81)90044-X"},{"key":"atypb17","first-page":"931","volume":"29","author":"Falikman D. I.","year":"1981","journal-title":"Mat. Zametki"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00019-3"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"J. Franklin and J. Lorenz,\n                      On the scaling of multidimensional matrices\n                      , Linear Algebra Appl., 114-115 (1989), pp. 717-735.","DOI":"10.1016\/0024-3795(89)90490-4"},{"key":"atypb20","unstructured":"W. C Franks and A. Moitra,\n                      Rigorous guarantees for Tyler's M-estimator via quantum expansion\n                      , in Proceedings of the 33rd Conference on Learning Theory, 2020, pp. 1601-1632."},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"A. Garg, L. Gurvits, R. Oliveira, and A. Wigderson,\n                      A deterministic polynomial time algorithm for non-commutative rational identity testing\n                      , in Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016, pp. 109-117.","DOI":"10.1109\/FOCS.2016.95"},{"key":"atypb22","unstructured":"A. Garg, L. Gurvits, R. Oliveira, and A. Wigderson,\n                      Operator Scaling: Theory and Applications\n                      ,arXiv:1511.03730, 2015."},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"A. Garg, L. Gurvits, R. Oliveira, and A. Wigderson,\n                      Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling\n                      , in Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), 2017, pp. 397-409.","DOI":"10.1145\/3055399.3055458"},{"key":"atypb24","first-page":"125","author":"Garg A.","year":"2018","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"A. Goel, M. Kapralov, and S. Khanna,\n                      Perfect matchings in $O(n \\log n)$ times in regular bipartite graphs\n                      , in Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), 2010, pp. 39-46.","DOI":"10.1145\/1806689.1806697"},{"key":"atypb26","unstructured":"C. Gon\u017aalez-Guil\u00e9n, M. Junge, and I. Nechita,\n                      Spectral gap of random quantum channels\n                      , presented at Workshop on Probabilistic Techniques and Quantum Information Theory, 2017."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01398933"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01388837"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"V. Guillemin and R. Sjamaar,\n                      Convexity Properties of Hamiltonian Group Actions\n                      , AMS, Providence, RI, 2005.","DOI":"10.1090\/crmm\/026"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"L. Gurvits,\n                      Hyperbolic polynomials approach to Van der Waerden\/Schrijver-Valiant like conjectures: Sharper bounds, simpler proofs and algorithmic applications\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), 2006, pp. 417-426.","DOI":"10.1145\/1132516.1132578"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.06.003"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"L. Gurvits and A. Samorodnitsky,\n                      A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume\n                      , in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), 2000, pp. 48-57.","DOI":"10.1145\/335305.335311"},{"key":"atypb33","unstructured":"L. Gurvits and P. N. Yianilos,\n                      The Deflation-Inflation Method for Certain Semidefinite Programming and Maximum Determinant Completion Problems\n                      , Technical report, NECI, 1998."},{"key":"atypb34","unstructured":"L. Hamilton and A. Moitra,\n                      The Paulsen Problem Made Simple\n                      ,arXiv:1809.04726, 2018."},{"key":"atypb35","first-page":"354","volume":"30","author":"Hardt M.","year":"2013","journal-title":"PMLR"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"N. Harms,\n                      Testing Halfspaces over Rotation-Invariant Distributions\n                      ,arXiv:1811.00139, 2018.","DOI":"10.1137\/1.9781611975482.44"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.76.032315"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2003.07.012"},{"key":"atypb39","unstructured":"R. A. Horn and C. R. Johnson,\n                      Matrix Analysis\n                      , 2nd ed., Cambridge University Press, Cambridge, UK, 2012."},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"R. A. Horn and C. R. Johnson,\n                      Topics in Matrix Analysis\n                      , Cambridge University Press, Cambridge, UK, 1991.","DOI":"10.1017\/CBO9780511840371"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"M. Idel,\n                      A Review of Matrix Scaling and Sinkhorn's Normal Form for Matrices and Positive Maps\n                      ,arXiv:1609.06349, 2016.","DOI":"10.1016\/j.laa.2014.12.031"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895289765"},{"key":"atypb43","first-page":"233","author":"Kempf G.","year":"1979","journal-title":"New York"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"F. C. Kirwan,\n                      Cohomology of Quotients in Symplectic and Algebraic Geometry\n                      , Math. Notes 31, Princeton University Press, Princeton, NJ, 1984.","DOI":"10.1515\/9780691214566"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/BF01388838"},{"key":"atypb46","first-page":"199","author":"Krivelevich M.","year":"2006","journal-title":"Budapest"},{"key":"atypb47","unstructured":"T. C. Kwok, L. C. Lau, Y. T. Lee, and A. Ramachandran,\n                      The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis\n                      , CoRR abs\/1710.02587, 2017."},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1007\/BF01233426"},{"key":"atypb49","first-page":"644","author":"Linial N.","year":"1998","journal-title":"Proceedings of STOC"},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"A. Madry,\n                      Navigating central path with electrical flows: From flows to matchings, and back\n                      , in Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2013, pp. 253-262.","DOI":"10.1109\/FOCS.2013.35"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00296"},{"key":"atypb52","doi-asserted-by":"crossref","unstructured":"A. Nikolov and M. Singh,\n                      Maximizing determinants under partition constraints\n                      , in Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), 2016, pp. 192-201.","DOI":"10.1145\/2897518.2897649"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(99)00212-8"},{"key":"atypb54","doi-asserted-by":"crossref","unstructured":"G. Peyr\u00e9 and M. Cuturi,\n                      Computational Optimal Transport\n                      ,arXiv:1803.00567, 2018.","DOI":"10.1561\/9781680835519"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOP1036"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703591"},{"key":"atypb57","unstructured":"A. Slav\u00edk,\n                      Product Integration, Its History and Applications\n                      , Matfyzpress, Prague, 2007."},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1016\/S1063-5203(03)00023-X"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2007.05.043"},{"key":"atypb60","doi-asserted-by":"crossref","unstructured":"T. Tao,\n                      Topics in Random Matrix Theory\n                      , Grad. Stud. Math. 132, AMS, Providence, RI, 2012.","DOI":"10.1090\/gsm\/132"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.839492"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1561\/2200000048"},{"key":"atypb63","doi-asserted-by":"crossref","unstructured":"J. Watrous,\n                      The Theory of Quantum Information\n                      , Cambridge University Press, Cambridge, UK, 2018.","DOI":"10.1017\/9781316848142"},{"key":"atypb64","unstructured":"J. Watrous,\n                      private communication\n                      , 2018."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1315981","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:12Z","timestamp":1787337192000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1315981"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":64,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1315981"],"URL":"https:\/\/doi.org\/10.1137\/20m1315981","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}