The positive semidefinite Grothendieck problem with rank constraint

Abstract

Given a positive integer n and a positive semidefinite matrix A = (A_{ij}) of size m x m, the positive semidefinite Grothendieck problem with rank-n-constraint (SDP_n) is maximize \sum_{i=1}^m \sum_{j=1}^m A_{ij} x_i \cdot x_j, where x_1, ..., x_m \in S^{n-1}. In this paper we design a polynomial time approximation algorithm for SDP_n achieving an approximation ratio of γ(n) = \frac{2}{n}(\frac{Γ((n+1)/2)}{Γ(n/2)})^2 = 1 - Θ(1/n). We show that under the assumption of the unique games conjecture the achieved approximation ratio is optimal: There is no polynomial time algorithm which approximates SDP_n with a ratio greater than γ(n). We improve the approximation ratio of the best known polynomial time algorithm for SDP_1 from 2/πto 2/(πγ(m)) = 2/π+ Θ(1/m), and we show a tighter approximation ratio for SDP_n when A is the Laplacian matrix of a graph with nonnegative edge weights.

(v3) to appear in Proceedings of the 37th International Colloquium on Automata, Languages and Programming, 12 pages

References in corpus (1)

• A generalized Grothendieck inequality and entanglement in XOR games

Cited by in corpus (5)

• Grothendieck inequalities for semidefinite programs with rank constraint
• Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups
• Efficient SDP Inference for Fully-connected CRFs Based on Low-rank Decomposition
• Relaxations for inference in restricted Boltzmann machines
• A sub-constant improvement in approximating the positive semidefinite Grothendieck problem