Published October 2, 2014
| Published + Submitted
Journal Article
Open
Efficient Rounding for the Noncommutative Grothendieck Inequality
- Creators
- Naor, Assaf
- Regev, Oded
-
Vidick, Thomas
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.
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.Attached Files
Published - v010a011.pdf
Submitted - 1210.7656.pdf
Files
1210.7656.pdf
Files
(780.6 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:170ab7397719932a4c82e98467d62f63
|
373.7 kB | Preview Download |
|
md5:828e51c550e66985e2d1e7e643424b1f
|
406.8 kB | Preview Download |
Additional details
- Eprint ID
- 104688
- Resolver ID
- CaltechAUTHORS:20200731-152129927
- CCF-0832795
- NSF
- 2010021
- Binational Science Foundation (USA-Israel)
- Alfred P. Sloan Foundation
- Simons Foundation
- European Research Council (ERC)
- CCF-0844626
- NSF
- MOE2012-T3-1-009
- Ministry of Education (Singapore)
- Created
-
2020-07-31Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field