Convergence of SDP hierarchies for polynomial optimization on the hypersphere

Abstract

We show how to bound the accuracy of a family of semi-definite programming relaxations for the problem of polynomial optimization on the hypersphere. Our method is inspired by a set of results from quantum information known as quantum de Finetti theorems. In particular, we prove a de Finetti theorem for a special class of real symmetric matrices to establish the existence of approximate representing measures for moment matrix relaxations.

45 pages, amsmath, comments welcome, for readers in quantum information: contains de Finetti theorem, v2: improved explanations, additional bound

References in corpus (1)

• Hypercontractivity, Sum-of-Squares Proofs, and their Applications

Cited by in corpus (15)

• Sum-of-squares proofs and the quest toward optimal algorithms
• The sum-of-squares hierarchy on the sphere, and applications in quantum information theory
• Tensor principal component analysis via sum-of-squares proofs
• Extended geometries
• Can you compute the operator norm?
• Double supergeometry
• Limitations of semidefinite programs for separable states and entangled games
• Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
• Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization
• A fermionic de Finetti theorem
• Convergence analysis for Lasserre's measure--based hierarchy of upper bounds for polynomial optimization
• Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
• A hierarchy of eigencomputations for polynomial optimization on the sphere
• Semidefinite Relaxations of Products of Nonnegative Forms on the Sphere
• Approximation Algorithms for Optimization of Real-Valued General Conjugate Complex Forms