Efficient Rounding for the Noncommutative Grothendieck Inequality

Abstract

The classical Grothendieck inequality has applications to the design of approximation algorithms for $\cclass{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.

Published in Theory of Computing, Volume 10 (2014), Article 11; Received: February 16, 2013, Revised: August 11, 2014, Published: October 2, 2014

References in corpus (1)

• The Effros-Ruan conjecture for bilinear forms on C^*-algebras

Cited by in corpus (4)

• Semidefinite descriptions of the convex hull of rotation matrices
• Tight Hardness of the Non-commutative Grothendieck Problem
• Expanding the reach of quantum optimization with fermionic embeddings
• Norms of structured random matrices