A Caltech Library Service

Efficient Rounding for the Noncommutative Grothendieck Inequality

Naor, Assaf and Regev, Oded and Vidick, Thomas (2013) Efficient Rounding for the Noncommutative Grothendieck Inequality. In: Proceedings of the forty-fifth annual ACM symposium on Theory of computing. ACM , New York, NY, pp. 71-80. ISBN 978-1-4503-2029-0.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The classical Grothendieck inequality has applications to the design of approximation algorithms for NP-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a constant-factor polynomial time approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principle component analysis and the orthogonal Procrustes problem.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper ItemJournal Article
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2013 ACM. We thank Daniel Dadush and Raghu Meka for useful discussions. Supported by NSF grant CCF-0832795, BSF grant 2010021, the Packard Foundation and the Simons Foundation. Part of this work was completed while A. N. was visiting Université de Paris Est Marne-la-Vallée. Supported by a European Research Council (ERC) Starting Grant. Part of the work done while the author was with the CNRS, DI, ENS, Paris. Supported by the National Science Foundation under Grant No. 0844626.
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2010021
David and Lucile Packard FoundationUNSPECIFIED
Simons FoundationUNSPECIFIED
European Research Council (ERC)UNSPECIFIED
Subject Keywords:Grothendieck inequality, rounding algorithm, semidefinite programming, principal component analysis
Record Number:CaltechAUTHORS:20140910-115031387
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49545
Deposited By: Ruth Sustaita
Deposited On:10 Sep 2014 19:48
Last Modified:10 Nov 2021 18:45

Repository Staff Only: item control page