Efficient rounding for the noncommutative grothendieck inequality

Assaf Naor; Oded Regev; Thomas Vidick

doi:10.1145/2488608.2488618

Efficient rounding for the noncommutative grothendieck inequality

Assaf Naor, Oded Regev, Thomas Vidick

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
Pages	71-80
Number of pages	10
DOIs	https://doi.org/10.1145/2488608.2488618
State	Published - 2013
Event	45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States Duration: Jun 1 2013 → Jun 4 2013

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Other

Other	45th Annual ACM Symposium on Theory of Computing, STOC 2013
Country/Territory	United States
City	Palo Alto, CA
Period	6/1/13 → 6/4/13

Keywords

Grothendieck inequality
Principal component analysis
Rounding algorithm
Semidefinite programming

ASJC Scopus subject areas

Software

Access to Document

10.1145/2488608.2488618

Cite this

Naor, A, Regev, O & Vidick, T 2013, Efficient rounding for the noncommutative grothendieck inequality. in STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 71-80, 45th Annual ACM Symposium on Theory of Computing, STOC 2013, Palo Alto, CA, United States, 6/1/13. https://doi.org/10.1145/2488608.2488618

@inproceedings{13af15d9fbbb4f51a4ad82d914013a19,

title = "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.",

keywords = "Grothendieck inequality, Principal component analysis, Rounding algorithm, Semidefinite programming",

author = "Assaf Naor and Oded Regev and Thomas Vidick",

year = "2013",

doi = "10.1145/2488608.2488618",

language = "English (US)",

isbn = "9781450320290",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

pages = "71--80",

booktitle = "STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing",

note = "45th Annual ACM Symposium on Theory of Computing, STOC 2013 ; Conference date: 01-06-2013 Through 04-06-2013",

}

TY - GEN

T1 - Efficient rounding for the noncommutative grothendieck inequality

AU - Naor, Assaf

AU - Regev, Oded

AU - Vidick, Thomas

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Grothendieck inequality

KW - Principal component analysis

KW - Rounding algorithm

KW - Semidefinite programming

UR - http://www.scopus.com/inward/record.url?scp=84879833771&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879833771&partnerID=8YFLogxK

U2 - 10.1145/2488608.2488618

DO - 10.1145/2488608.2488618

M3 - Conference contribution

AN - SCOPUS:84879833771

SN - 9781450320290

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 71

EP - 80

BT - STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing

T2 - 45th Annual ACM Symposium on Theory of Computing, STOC 2013

Y2 - 1 June 2013 through 4 June 2013

ER -

Efficient rounding for the noncommutative grothendieck inequality

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this