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]