Theory of Computing
-------------------
Title : Efficient Rounding for the Noncommutative Grothendieck Inequality
Authors : Assaf Naor, Oded Regev, and Thomas Vidick
Volume : 10
Number : 11
Pages : 257-295
URL : https://theoryofcomputing.org/articles/v010a011
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.