Efficient rounding for the noncommutative grothendieck inequality

Assaf Naor, Oded Regev, Thomas Vidick

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationSTOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
Pages71-80
Number of pages10
DOIs
StatePublished - 2013
Event45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States
Duration: Jun 1 2013Jun 4 2013

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other45th Annual ACM Symposium on Theory of Computing, STOC 2013
CountryUnited States
CityPalo Alto, CA
Period6/1/136/4/13

Keywords

  • Grothendieck inequality
  • Principal component analysis
  • Rounding algorithm
  • Semidefinite programming

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Efficient rounding for the noncommutative grothendieck inequality'. Together they form a unique fingerprint.

  • Cite this

    Naor, A., Regev, O., & Vidick, T. (2013). Efficient rounding for the noncommutative grothendieck inequality. In STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing (pp. 71-80). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2488608.2488618