Matrix and Operator Scaling

We will study papers on matrix and operator scaling and their applications. In matrix scaling, given is a nonnegative matrix A, and the question is whether diagonal matrices L and R exist such that A'=LAR is (approximately) doubly stochastic. This classical problem has several applications in numerical analysis, algebra, and combinatorics, including applications to permanent approximation and connections to matchings. Operator scaling gives a far-reaching extension, and has deep connections and applications in quantum information theory, invariant theory, functional analysis, and more. A crucial application is to the non-commutative Edmonds' rank computation problem. The seminar will cover survey papers and articles on algorithms for matrix and operator scaling, the non-commutative Edmonds' problem, and their applications.

• Seminars will be held starting on week of 18 November, Wednesday and Friday 14:15-15:45, with approval talks on the same days 16:15-17:45.
• A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
• The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
• Each participant has to write a summary consisting of one or two pages.
• Each participant has to give an approval talk (typically three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.

• Idel, M. (2016). A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps. arXiv preprint arXiv:1609.06349.
• Linial, N., Samorodnitsky, A., & Wigderson, A. (2000). A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Combinatorica, 20(4), 545-568.
• Gurvits, L. & Samorodnitsky A. (2002). A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary. Discrete & Computational Geometry, 27, 531-550.
• Gurvits, L. (2004). Classical complexity and quantum entanglement. Journal of Computer and System Sciences, 69(3), 448-484.
• Garg, A., Gurvits, L., Oliveira, R., & Wigderson, A. (2020). Operator scaling: theory and applications. Foundations of Computational Mathematics, 20(2), 223-290.
• Garg, A., Gurvits, L., Oliveira, R., & Wigderson, A. (2018). Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. Geom. Funct. Anal, 28, 100-145.
• Ivanyos, G., Qiao, Y., & Subrahmanyam, K. (2018). Constructive non-commutative rank computation is in deterministic polynomial time. Computational Complexity, 27, 561-593.
• Hamada, M., & Hirai, H. (2021). Computing the nc-rank via discrete convex optimization on CAT (0) spaces. SIAM Journal on Applied Algebra and Geometry, 5(3), 455-478.