Cole Franks
ABSTRACT
The completely positive maps, a generalization of the nonnegative matrices, are a well-studied class of maps from n× n matrices to m× m matrices. The existence of the operator analogues of doubly stochastic scalings of matrices, the study of which is known as operator scaling, is equivalent to a multitude of problems in computer science and mathematics such rational identity testing in non-commuting variables, noncommutative rank of symbolic matrices, and a basic problem in invariant theory (Garg et. al., 2016).
We study operator scaling with specified marginals, which is the operator analogue of scaling matrices to specified row and column sums (or marginals). We characterize the operators which can be scaled to given marginals, much in the spirit of the Gurvits’ algorithmic characterization of the operators that can be scaled to doubly stochastic (Gurvits, 2004). Our algorithm, which is a modified version of Gurvits’ algorithm, produces approximate scalings in time poly(n,m) whenever scalings exist. A central ingredient in our analysis is a reduction from operator scaling with specified marginals to operator scaling in the doubly stochastic setting.
Instances of operator scaling with specified marginals arise in diverse areas of study such as the Brascamp-Lieb inequalities, communication complexity, eigenvalues of sums of Hermitian matrices, and quantum information theory. Some of the known theorems in these areas, several of which had no algorithmic proof, are straightforward consequences of our characterization theorem. For instance, we obtain a simple algorithm to find, when it exists, a tuple of Hermitian matrices with given spectra whose sum has a given spectrum. We also prove new theorems such as a generalization of Forster’s theorem (Forster, 2002) concerning radial isotropic position.
Supplemental Material
- Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. 2017. Much faster algorithms for matrix scaling. arXiv preprint arXiv:1704.02315 (2017).Google Scholar
- Franck Barthe. 1998. On a reverse form of the Brascamp-Lieb inequality. Inventiones mathematicae 134, 2 (1998), 335–361.Google Scholar
- Peter Bürgisser, Matthias Christandl, Ketan D Mulmuley, and Michael Walter. 2017. Membership in moment polytopes is in NP and coNP. SIAM J. Comput. 46, 3 (2017), 972–991. arXiv: 1511.03675Google ScholarCross Ref
- Michael B Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. 2017.Google Scholar
- Matrix Scaling and Balancing via Box Constrained Newton’s Method and Interior Point Methods. arXiv preprint arXiv:1704.02310 (2017).Google Scholar
- Harm Derksen and Visu Makam. 2017.Google Scholar
- Polynomial degree bounds for matrix semi-invariants. Advances in Mathematics 310 (2017), 44–63.Google Scholar
- Jack Edmonds. 1970.Google Scholar
- Submodular functions, matroids, and certain polyhedra. Edited by G. Goos, J. Hartmanis, and J. van Leeuwen 11 (1970).Google Scholar
- Jürgen Forster. 2002. A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. System Sci. 65, 4 (2002), 612–625. Google ScholarDigital Library
- Cole Franks. 2018.Google Scholar
- Operator scaling with specified marginals. arXiv preprint arXiv:1801.01412 (2018).Google Scholar
- Shmuel Friedland. 2016.Google Scholar
- On Schrodinger’s bridge problem. arXiv preprint arXiv:1608.05862 (2016).Google Scholar
- William Fulton. 2000. Eigenvalues, invariant factors, highest weights, and Schubert calculus. Bull. Amer. Math. Soc. 37, 3 (2000), 209–249.Google ScholarCross Ref
- Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. 2016.Google Scholar
- Algorithmic aspects of Brascamp-Lieb inequalities. arXiv preprint arXiv:1607.06711 (2016).Google Scholar
- Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. 2016. A deterministic polynomial time algorithm for non-commutative rational identity testing. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on. IEEE, 109–117.Google ScholarCross Ref
- Tryphon T Georgiou and Michele Pavon. 2015. Positive contraction mappings for classical and quantum Schrödinger systems. J. Math. Phys. 56, 3 (2015), 033301.Google ScholarCross Ref
- Leonid Gurvits. 2004. Classical complexity and quantum entanglement. J. Comput. System Sci. 69, 3 (2004), 448–484. Google ScholarDigital Library
- Moritz Hardt and Ankur Moitra. 2013.Google Scholar
- Algorithms and hardness for robust subspace recovery. In Conference on Learning Theory. 354–375.Google Scholar
- Alfred Horn. 1954.Google Scholar
- Doubly stochastic matrices and the diagonal of a rotation matrix. American Journal of Mathematics 76, 3 (1954), 620–630.Google Scholar
- Alfred Horn. 1962. Eigenvalues of sums of Hermitian matrices. Pacific J. Math. 12, 1 (1962), 225–241.Google ScholarCross Ref
- A Jamiołkowski. 1974. An effective method of investigation of positive maps on the set of positive definite operators. Reports on Mathematical Physics 5, 3 (1974), 415–424.Google ScholarCross Ref
- Alexander A Klyachko. 1998. Stable bundles, representation theory and Hermitian operators. Selecta Mathematica, New Series 4, 3 (1998), 419–445.Google ScholarCross Ref
- Allen Knutson and Terence Tao. 2000.Google Scholar
- Honeycombs and sums of Hermitian matrices. (2000). arXiv: math/0009048 https://arxiv.org/abs/math/0009048Google Scholar
- Nathan Linial, Alex Samorodnitsky, and Avi Wigderson. 1998. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. In Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM, 644–652. Google ScholarDigital Library
- James S. Milne. 2017. Algebraic Geometry (v6.02). (2017), 221 pages. Available at www.jmilne.org/math/.Google Scholar
- Ketan D Mulmuley, Hariharan Narayanan, and Milind Sohoni. 2012. Geometric complexity theory III: on deciding nonvanishing of a Littlewood–Richardson coefficient. Journal of Algebraic Combinatorics 36, 1 (2012), 103–110. Google ScholarDigital Library
- D Mumford. 1999.Google Scholar
- The red book of varieties and schemes, Second, expanded edition, volume 1358 of LNM. (1999).Google Scholar
- Uriel G Rothblum and Hans Schneider. 1989. Scalings of matrices which have prespecified row sums and column sums via optimization. Linear Algebra Appl. 114 (1989), 737–764.Google ScholarCross Ref
- Richard Sinkhorn. 1964. A relationship between arbitrary positive matrices and doubly stochastic matrices. The annals of mathematical statistics 35, 2 (1964), 876–879.Google Scholar
- Michael Walter, Brent Doran, David Gross, and Matthias Christandl. 2013. Entanglement polytopes: multiparticle entanglement from single-particle information. Science 340, 6137 (2013), 1205–1208.Google Scholar
Index Terms
- Operator scaling with specified marginals
Recommendations
Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of ComputingWe propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the ...
The Paulsen problem, continuous operator scaling, and smoothed analysis
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of ComputingThe Paulsen problem is a basic open problem in operator theory: Given vectors u1, …, un ∈ ℝd that are є-nearly satisfying the Parseval’s condition and the equal norm condition, is it close to a set of vectors v1, …, vn ∈ ℝd that exactly satisfy the ...
Spectral Analysis of Matrix Scaling and Operator Scaling
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 ...
Comments