Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2013 | Submitted
Book Section - Chapter Open

Efficient Rounding for the Noncommutative Grothendieck Inequality

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.

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.

Attached Files

Submitted - 1210.7656v1.pdf

Files

1210.7656v1.pdf
Files (373.7 kB)
Name Size Download all
md5:170ab7397719932a4c82e98467d62f63
373.7 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 17, 2023