The Paulsen Problem Continuous Operator Scaling and Smoothed Analysis S

Abstract

The Paulsen problem was once thought to be one of the most intractable problems in frame theory. It was resolved in a recent tour-de-force work of Kwok, Lau, Lee and Ramachandran. In particular, they showed that every ϵ-nearly equal norm Parseval frame in d dimensions is within squared distance O(ϵ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(ϵd ²).

References

1. B. Alexeev, J. Cahill and D. Mixon, Full spark frames, Journal of Fourier Analysis and Applications 18 (2012) 1167–1194.

   Article  MathSciNet  Google Scholar

2. K. Ball, Volumes of sections of cubes and related problems in Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics, Vol. 1376, Springer, Berlin, 1989, pp. 251–260.

   Chapter  Google Scholar

3. F. Barthe, On a reverse form of the Brascamp—Lieb inequality Inventiones Mathematicae 134 (1998), 335–361.

   Article  MathSciNet  Google Scholar

4. J. Bennett, A. Carbery, M. Christ and T. Tao, The Brascamp—Lieb inequalities: Finiteness, structure, and extremals Geometric and Functional Analysis 17 (2008), 1343–1415.

   Article  MathSciNet  Google Scholar

5. B. G. Bodman and P. G. Casazza, The road to equal-norm Parseval frames Journal of Functional Analysis 258 (2010), 397–420.

   Article  MathSciNet  Google Scholar

6. J. Cahill and P. G. Casazza, The Paulsen problem in operator theory, Operators and Matrices 7 (2013) 117–130.

   Article  MathSciNet  Google Scholar

7. . P. G. Casazza, The Kadison—Singer and Paulsen problems in finite frame theory, in Finite Frames, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, New York, 2013, pp. 381–413.

   Chapter  Google Scholar

8. P. G. Casazza, M. Fickus and D. Mixon, Auto-tuning unit norm frames, Applied and Computational Harmonic Analysis 32 (2012) 1–15.

   Article  MathSciNet  Google Scholar

9. P. G. Casazza and R. G. Lynch, A brief introduction to Hilbert space frame theory and its applications, in Finite Frame Theory, Proceedings of Symposia in Applied Mathematics, Vol. 73, American Mathematical Society, Providence, RI, 2016, 1–51.

   MATH  Google Scholar

10. Z. Dvir, S. Saraf and A. Wigderson, Superquadratic lower bound for 3-query locally correctable codes over the reals, Theory of Computing 13 (2017) 1–36.

    Article  MathSciNet  Google Scholar

11. J. Edmonds, Submodular functions, matroids, and certain polyhedra, in Combinatorial Structures and Their Applications (Proceedings of the Calgary International Conference, Calgary, AB, 1969), Gordon and Breach, New York, 1970, pp. 69–87.

    Google Scholar

12. J. Forster, A linear lower bound on the unbounded error probabilistic community complexity, Journal of Computer and System Sciences 65 (2002) 612–625.

    Article  MathSciNet  Google Scholar

13. C. Franks and A. Moitra, Rigorous guarantees for Tyler's M-estimator via quantum expansion, in Proceedings of Thirty Third Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 125, PMLR Press, 2020, pp. 1601–1632.

14. A. Garg, L. Gurvits, R. Oliveira and A. Wigderson, A deterministic polynomial time algorithm for non-commutative rational identity testing, in 57th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2016, IEEE Computer Society, Los Alamitos, CA, 2016, pp. 109–117.

    Chapter  Google Scholar

15. A. Garg, L. Gurvits, R. Oliveira and A. Wigderson, Algorithmic and optimization aspects of Brascamp—Lieb inequalities, via operator scaling, in STOC'17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, pp. 397–409.

    Chapter  Google Scholar

16. L. Gurvits, Classical complexity and quantum entanglement, Journal of Computer and System Sciences 69 (2004) 448–484.

    Article  MathSciNet  Google Scholar

17. M. Hardt and A. Moitra, Algorithms and hardness for robust subspace recovery in Proceedings of the 26th Annual Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 30, PMLR, 2013, pp. 354–375.

18. T. C. Kwok, L. C. Lau, Y. T. Lee and A. Ramachandran, The Paulsen problem, continuous operator scaling, and smoothed analysis, in STOC'18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2018, pp. 182–189.

    Chapter  Google Scholar

19. T. C. Kwok, L. C. Lau, Y. T. Lee and A. Ramachandran, The Paulsen problem, continuous operator scaling, and smoothed analysis, https://arxiv.org/abs/1710.02587.

20. D. G. Mixon, Four open problems in frame theory, in Frames and Algebraic and Combinatorial Geometry, Universität Bremen, Bremen, 2015, https://www.alta.uni-bremen.de/FAG15/slides/Mixon.pdf.

    Google Scholar

Download references

Acknowledgements

We thank Avi Wigderson and an anonymous referee for numerous helpful comments on earlier versions of our paper.

Author information

Authors and Affiliations

1. Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, 02199, USA

   Linus Hamilton

2. Department of Mathematics and Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, 02199, USA

   Ankur Moitra

Corresponding author

Correspondence to Ankur Moitra.

Additional information

The results in this full paper were briefly announced in the conference ITCS 2019 but without any accompanying proofs.

This work was supported in part by a Fannie and John Hertz Foundation Fellowship.

This work was supported in part by NSF CAREER Award CCF-1453261, NSF Large CCF-1565235, a David and Lucile Packard Fellowship and an ONR Young Investigator Award.

About this article

Cite this article

Hamilton, L., Moitra, A. The Paulsen problem made simple. Isr. J. Math. 246, 299–313 (2021). https://doi.org/10.1007/s11856-021-2245-7

Download citation

• Received: 09 January 2020

• Revised: 17 August 2020

• Published: 25 November 2021

• Issue Date: December 2021

• DOI : https://doi.org/10.1007/s11856-021-2245-7

thornepopes1970.blogspot.com

Source: https://link.springer.com/article/10.1007/s11856-021-2245-7

Share this post