LIPIcs.ITCS.2019.41.pdf
- Filesize: 373 kB
- 6 pages
Document
The Paulsen Problem Made Simple
Authors
-
Part of:
Volume:
10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Innovations in Theoretical Computer Science Conference (ITCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-01-08
Cite As Get BibTex
Linus Hamilton and Ankur Moitra. The Paulsen Problem Made Simple. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 41:1-41:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.41
Abstract
The Paulsen problem is a basic problem in operator theory that was resolved in a recent tour-de-force work of Kwok, Lau, Lee and Ramachandran. In particular, they showed that every epsilon-nearly equal norm Parseval frame in d dimensions is within squared distance O(epsilon d^{13/2}) of an equal norm Parseval frame. We give a dramatically simpler proof based on the notion of radial isotropic position, and along the way show an improved bound of O(epsilon d^2).
Subject Classification
ACM Subject Classification
- Theory of computation → Design and analysis of algorithms
Keywords
- radial isotropic position
- operator scaling
- Paulsen problem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Keith Ball. Volumes of sections of cubes and related problems. In Geometric aspects of functional analysis, pages 251-260. Springer, 1989.
-
Franck Barthe. On a reverse form of the Brascamp-Lieb inequality. Inventiones mathematicae, 134(2):335-361, 1998.
-
Jonathan Bennett, Anthony Carbery, Michael Christ, and Terence Tao. The Brascamp-Lieb inequalities: finiteness, structure and extremals. Geometric and Functional Analysis, 17(5):1343-1415, 2008.
-
Jameson Cahill and Peter G Casazza. The Paulsen problem in operator theory. submitted to Operators and Matrices, 2011.
-
Zeev Dvir, Shubhangi Saraf, and Avi Wigderson. Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals. Theory of Computing, 13(1):1-36, 2017.
-
Jack Edmonds. Submodular functions, matroids, and certain polyhedra. Combinatorial structures and their applications, pages 69-87, 1970.
-
Jürgen Forster. A linear lower bound on the unbounded error probabilistic communication complexity. Journal of Computer and System Sciences, 65(4):612-625, 2002.
-
Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. A deterministic polynomial time algorithm for non-commutative rational identity testing. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 109-117. IEEE, 2016.
-
Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling. Geometric and Functional Analysis, 28(1):100-145, 2018.
-
Leonid Gurvits. Classical complexity and quantum entanglement. Journal of Computer and System Sciences, 69(3):448-484, 2004.
-
Moritz Hardt and Ankur Moitra. Algorithms and hardness for robust subspace recovery. In Conference on Learning Theory, pages 354-375, 2013.
-
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, and Akshay Ramachandran. The Paulsen problem, continuous operator scaling, and smoothed analysis. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 182-189. ACM, 2018.