Naor, Assaf and Regev, Oded and Vidick, Thomas (2014) Efficient Rounding for the Noncommutative Grothendieck Inequality. Theory of Computing, 10 (1). pp. 257-295. ISSN 1557-2862. doi:10.4086/toc.2014.v010a011. https://resolver.caltech.edu/CaltechAUTHORS:20200731-152129927
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Published Version
Creative Commons Attribution. 406kB |
|
PDF
- Submitted Version
See Usage Policy. 373kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200731-152129927
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.
| Item Type: | Article | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||||||||||||
| ORCID: |
| ||||||||||||||||
| Additional Information: | © 2014 Assaf Naor, Oded Regev, and Thomas Vidick. Creative Commons License Creative Commons License Attribution Licensed under a Creative Commons Attribution License (CC-BY). Received: February 16, 2013; Revised: August 11, 2014; Published: October 2, 2014. An extended abstract of this paper appeared in the Proceedings of the 45th Annual ACM Symposium on Theory of Computing, 2013. 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. Partially supported by the National Science Foundation under Grant No. 0844626 and by the Ministry of Education, Singapore under the Tier 3 grant MOE2012-T3-1-009. We thank Daniel Dadush and Raghu Meka for useful discussions. | ||||||||||||||||
| Funders: |
| ||||||||||||||||
| Subject Keywords: | approximation algorithms, Grothendieck inequality, semidefinite programming, principal component analysis | ||||||||||||||||
| Issue or Number: | 1 | ||||||||||||||||
| Classification Code: | ACM Classification: G.1.6; AMS Classification: 68W25 | ||||||||||||||||
| DOI: | 10.4086/toc.2014.v010a011 | ||||||||||||||||
| Record Number: | CaltechAUTHORS:20200731-152129927 | ||||||||||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20200731-152129927 | ||||||||||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||
| ID Code: | 104688 | ||||||||||||||||
| Collection: | CaltechAUTHORS | ||||||||||||||||
| Deposited By: | Tony Diaz | ||||||||||||||||
| Deposited On: | 31 Jul 2020 22:37 | ||||||||||||||||
| Last Modified: | 16 Nov 2021 18:34 |
Repository Staff Only: item control page
