CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20140910-115031387

[img]
Preview
PDF - Submitted Version
See Usage Policy.

373kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20140910-115031387

Abstract

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
https://doi.org/10.1145/2488608.2488618DOIArticle
https://arxiv.org/abs/1210.7656arXivDiscussion Paper
https://resolver.caltech.edu/CaltechAUTHORS:20200731-152129927Related ItemJournal Article
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
NSFCCF-0832795
Binational Science Foundation (USA-Israel)2010021
David and Lucile Packard FoundationUNSPECIFIED
Simons FoundationUNSPECIFIED
European Research Council (ERC)UNSPECIFIED
NSFCCF-0844626
Subject Keywords:Grothendieck inequality, rounding algorithm, semidefinite programming, principal component analysis
DOI:10.1145/2488608.2488618
Record Number:CaltechAUTHORS:20140910-115031387
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20140910-115031387
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49545
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:10 Sep 2014 19:48
Last Modified:10 Nov 2021 18:45

Repository Staff Only: item control page