The positive semidefinite Grothendieck problem with rank constraint

DOI10.1007/978-3-642-14165-2_4MaRDI QIDQ3587367zbMATH OpenOpenAlexFDO

Authors Jop Briët, Fernando Mário de Oliveira Filho, Frank Vallentin

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.5765

Mathematics Subject Classification ID

Quadratic programming (90C20) Randomized algorithms (68W20) Approximation algorithms (68W25)

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 gamma(n) = frac{2}{n}(frac{Gamma((n+1)/2)}{Gamma(n/2)})^2 = 1 - Theta(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 gamma(n). We improve the approximation ratio of the best known polynomial time algorithm for SDP_1 from 2/pi to 2/(pigamma(m)) = 2/pi + Theta(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.

Recommendations

• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• SDP gaps and UGC-hardness for max-cut-gain
• Towards computing the Grothendieck constant
• Grothendieck inequalities for semidefinite programs with rank constraint
• The Grothendieck constant is strictly smaller than Krivine's bound

Cited in

(14)

• Grothendieck’s Theorem, past and present
• Grothendieck-type inequalities in combinatorial optimization
• Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators
• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• Rational and real positive semidefinite rank can be different
• A generalized Grothendieck inequality and nonlocal correlations that require high entanglement
• Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
• On the largest Bell violation attainable by a quantum state
• Grothendieck constant is norm of Strassen matrix multiplication tensor
• Grothendieck inequalities for semidefinite programs with rank constraint
• A note on approximating quadratic programming with rank constraint
• scientific article; zbMATH DE number 7758361 (Why is no real title available?)
• Sharp kernel clustering algorithms and their associated Grothendieck inequalities
• On sketching the \(q\) to \(p\) norms

This page was built for publication: The positive semidefinite Grothendieck problem with rank constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587367)