Efficient Rounding for the Noncommutative Grothendieck Inequality
by Assaf Naor, Oded Regev, and Thomas Vidick
Theory of Computing, Volume 10(11), pp. 257-295, 2014
Bibliography with links to cited articles
[1] Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor: Quadratic forms on graphs. Invent. Math., 163(3):499–522, 2006. Preliminary version in STOC’05. [doi:10.1007/s00222-005-0465-9]
[2] Noga Alon and Assaf Naor: Approximating the cut-norm via Grothendieck’s inequality. SIAM J. Comput., 35(4):787–803, 2006. Preliminary version in STOC’04. [doi:10.1137/S0097539704441629]
[3] Jos M. F. ten Berge: Orthogonal Procrustes rotation for two or more matrices. Psychometrika, 42(2):267–276, 1977. [doi:10.1007/BF02294053]
[4] Ph. Bourgeois: Extension de la méthode Procuste à la comparaison de nuages de points situés dans des espaces de dimensions différentes. RAIRO Rech. Opér., 16(1):45–63, 1982. Found at EUDML.
[5] Mark Braverman, Konstantin Makarychev, Yury Makarychev, and Assaf Naor: The Grothendieck constant is strictly smaller than Krivine’s bound. Forum of Mathematics, Pi, 1(e4), 2013. Preliminary version in FOCS’11. [doi:10.1017/fmp.2013.4]
[6] Eduardo R. Caianiello and Renato M. Capocelli: On form and language: the Procrustes algorithm for feature extraction. Kybernetik, 8(6):223–233, 1971. [doi:10.1007/BF00288751]
[7] Richard Cleve, Peter Høyer, Ben Toner, and John Watrous: Consequences and limits of nonlocal strategies. In Proc. 19th IEEE Conf. on Computational Complexity (CCC’04), pp. 236–249, 2004. [doi:10.1109/CCC.2004.1313847]
[8] Luc Devroye: Nonuniform Random Variate Generation. Springer, 1986. Found on author’s website.
[9] Joe Diestel, Hans Jarchow, and Andrew Tonge: Absolutely Summing Operators. Volume 43 of Cambridge Studies in Advanced Mathematics. Cambridge Univ. Press, 1995. [doi:10.1017/CBO9780511526138]
[10] Chris Ding, Ding Zhou, Xiaofeng He, and Hongyuan Zha: R1-PCA: Rotational invariant L1-norm principal component analysis for robust subspace factorization. In Proc. 23rd Internat. Conf. on Machine Learning (ICML’06), pp. 281–288. ACM Press, 2006. [doi:10.1145/1143844.1143880]
[11] Ian L. Dryden and Kanti V. Mardia: Statistical Shape Analysis. Wiley, 1998.
[12] Alan M. Frieze and Ravi Kannan: Quick approximation to matrices and applications. Combinatorica, 19(2):175–220, 1999. [doi:10.1007/s004930050052]
[13] Michel X. Goemans and David P. Williamson: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, 1995. Preliminary version in STOC’94. [doi:10.1145/227683.227684]
[14] John C. Gower: Generalized Procrustes analysis. Psychometrika, 40(1):33–51, 1975. [doi:10.1007/BF02291478]
[15] John C. Gower and Garmt B. Dijksterhuis: Procrustes Problems. Volume 30 of Oxford Statistical Science Series. Oxford University Press, 2004.
[16] Alexander Grothendieck: Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. São Paulo, 8:1–79, 1953.
[17] Martin Grötschel, László Lovász, and Alexander Schrijver: Geometric Algorithms and Combinatorial Optimization. Volume 2 of Algorithms and Combinatorics. Springer, second edition, 1993. [doi:10.1007/978-3-642-78240-4]
[18] Uffe Haagerup: The Grothendieck inequality for bilinear forms on C*-algebras. Adv. in Math., 56(2):93–116, 1985. [doi:10.1016/0001-8708(85)90026-X]
[19] Uffe Haagerup: A new upper bound for the complex Grothendieck constant. Israel J. Math., 60(2):199–224, 1987. [doi:10.1007/BF02790792]
[20] Uffe Haagerup and Takashi Itoh: Grothendieck type norms for bilinear forms on C*-algebras. J. Operator Theory, 34(2):263–283, 1995. [JOT].
[21] Uffe Haagerup and Magdalena Musat: The Effros-Ruan conjecture for bilinear forms on C*-algebras. Invent. Math., 174(1):139–163, 2008. [doi:10.1007/s00222-008-0137-7]
[22] Graham J. O. Jameson: The interpolation proof of Grothendieck’s inequality. In Proc. Edinburgh Math. Soc., volume 28, pp. 217–223, 1985. [doi:10.1017/S0013091500022653]
[23] Norman L. Johnson, Samuel Kotz, and Narayanaswamy Balakrishnan: Continuous Univariate Distributions. Volume 2. Wiley, 1995.
[24] William B. Johnson and Joram Lindenstrauss: Basic concepts in the geometry of Banach spaces. In Handbook of the geometry of Banach spaces, Vol. I, pp. 1–84. North-Holland, 2001. [doi:10.1016/S1874-5849(01)80003-6]
[25] Sten Kaijser: A simple-minded proof of the Pisier-Grothendieck inequality. In Ron Blei and Stuart Sidney, editors, Banach Spaces, Harmonic Analysis, and Probability Theory, volume 995 of Lecture Notes in Mathematics, pp. 33–55. Springer, 1983. [doi:10.1007/BFb0061887]
[26] Subhash Khot and Assaf Naor: Grothendieck-type inequalities in combinatorial optimization. Commun. Pure Appl. Math., 65(7):992–1035, 2012. [doi:10.1002/cpa.21398]
[27] Jean-Louis Krivine: Théorèmes de factorisation dans les espaces réticulés. In Séminaire Maurey-Schwartz 1973–1974: Espaces Lp, applications radonifiantes et géométrie des espaces de Banach, Exp. Nos. 22 et 23, p. 22. Centre de Math., École Polytech., Paris, 1974. Found at EUDML.
[28] Jean-Louis Krivine: Constantes de Grothendieck et fonctions de type positif sur les sphères. Adv. in Math., 31(1):16–30, 1979. [doi:10.1016/0001-8708(79)90017-3]
[29] Nojun Kwak: Principal component analysis based on L1-norm maximization. IEEE Trans. Pattern Anal. Mach. Intell., 30(9):1672–1680, 2008. [doi:10.1109/TPAMI.2008.114]
[30] Joram Lindenstrauss and Aleksander Pełczyński: Absolutely summing operators in Lp-spaces and their applications. Studia Math., 29(3):275–326, 1968. Found at EUDML.
[31] László Lovász and Balázs Szegedy: Szemerédi’s lemma for the analyst. Geom. Funct. Anal., 17(1):252–270, 2007. [doi:10.1007/s00039-007-0599-6]
[32] Michael McCoy and Joel A. Tropp: Two proposals for robust PCA using semidefinite programming. Electron. J. Statist., 5:1123–1160, 2011. [doi:10.1214/11-EJS636]
[33] Elisabeth Morand and Jérôme Pagès: Analyse factorielle multiple procustéenne. J. Soc. Fr. Stat. & Rev. Stat. Appl., 148(2):65–97, 2007. Found at EUDML.
[34] Assaf Naor, Oded Regev, and Thomas Vidick: Efficient rounding for the noncommutative Grothendieck inequality. In Proc. 45th STOC, pp. 71–80. ACM Press, 2013. [doi:10.1145/2488608.2488618]
[35] Arkadi Nemirovski: Sums of random symmetric matrices and quadratic optimization under orthogonality constraints. Math. Program., 109(2-3):283–317, 2007. [doi:10.1007/s10107-006-0033-0]
[36] Gilles Pisier: Grothendieck’s theorem for noncommutative C*-algebras, with an appendix on Grothendieck’s constants. J. Funct. Anal., 29(3):397–415, 1978. [doi:10.1016/0022-1236(78)90038-1]
[37] Gilles Pisier: Grothendieck’s theorem, past and present. Bull. Amer. Math. Soc., 49(2):237–323, 2012. [doi:10.1090/S0273-0979-2011-01348-9, arXiv:1101.4195]
[38] Gilles Pisier and Dimitri Shlyakhtenko: Grothendieck’s theorem for operator spaces. Invent. Math., 150(1):185–217, 2002. [doi:10.1007/s00222-002-0235-x]
[39] James A. Reeds: A new lower bound on the real Grothendieck constant. Unpublished manuscript, available at author’s home page, 1991.
[40] Oded Regev and Thomas Vidick: Elementary proofs of Grothendieck theorems for completely bounded norms. J. Operator Theory, 71(2):491–506, 2014. [doi:10.7900/jot.2012jul02.1947, arXiv:1206.4025]
[41] Oded Regev and Thomas Vidick: Quantum XOR games. ACM Transactions on Computation Theory (ToCT), 2014. To appear. Preliminary version in CCC’13. [arXiv:1207.4939]
[42] Alexander Shapiro and Johan D. Botha: Dual algorithms for orthogonal Procrustes rotations. SIAM J. Matrix Anal. Appl., 9(3):378–383, 1988. [doi:10.1137/0609032]
[43] Anthony So: Moment inequalities for sums of random matrices and their applications in optimization. Math. Program., 130(1):125–151, 2011. [doi:10.1007/s10107-009-0330-5]
[44] Mikkel B. Stegmann and David Delgado Gomez: A Brief Introduction to Statistical Shape Analysis, 2002. Available at IMM.
[45] Boris S. Tsirelson: Quantum analogues of the Bell inequalities. The case of two spatially separated domains. J. Soviet Math., 36(4):557–570, 1987. [doi:10.1007/BF01663472]