Efficient rounding for the noncommutative grothendieck inequality

Assaf Naor, Oded Regev, Thomas Vidick

Research output: Contribution to journalArticle

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 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.

Original languageEnglish (US)
Pages (from-to)257-295
Number of pages39
JournalTheory of Computing
Volume10
DOIs
StatePublished - Oct 2 2014

Keywords

  • Approximation algorithms
  • Grothendieck inequality
  • Principal component analysis
  • Semidefinite programming

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

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

  • Cite this