A Caltech Library Service

Efficient Rounding for the Noncommutative Grothendieck Inequality

Naor, Assaf and Regev, Oded and Vidick, Thomas (2014) Efficient Rounding for the Noncommutative Grothendieck Inequality. Theory of Computing, 10 (1). pp. 257-295. ISSN 1557-2862. doi:10.4086/toc.2014.v010a011.

[img] PDF - Published Version
Creative Commons Attribution.

[img] 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 polynomial-time constant-factor 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 principal component analysis and the orthogonal Procrustes problem.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper ItemConference Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2014 Assaf Naor, Oded Regev, and Thomas Vidick. Creative Commons License Creative Commons License Attribution Licensed under a Creative Commons Attribution License (CC-BY). Received: February 16, 2013; Revised: August 11, 2014; Published: October 2, 2014. An extended abstract of this paper appeared in the Proceedings of the 45th Annual ACM Symposium on Theory of Computing, 2013. 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. Partially supported by the National Science Foundation under Grant No. 0844626 and by the Ministry of Education, Singapore under the Tier 3 grant MOE2012-T3-1-009. We thank Daniel Dadush and Raghu Meka for useful discussions.
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2010021
Alfred P. Sloan FoundationUNSPECIFIED
Simons FoundationUNSPECIFIED
European Research Council (ERC)UNSPECIFIED
Ministry of Education (Singapore)MOE2012-T3-1-009
Subject Keywords:approximation algorithms, Grothendieck inequality, semidefinite programming, principal component analysis
Issue or Number:1
Classification Code:ACM Classification: G.1.6; AMS Classification: 68W25
Record Number:CaltechAUTHORS:20200731-152129927
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104688
Deposited By: Tony Diaz
Deposited On:31 Jul 2020 22:37
Last Modified:16 Nov 2021 18:34

Repository Staff Only: item control page