Sparse sum-of-squares certificates on finite abelian groups

Abstract

Let G be a finite abelian group. This paper is concerned with nonnegative functions on G that are sparse with respect to the Fourier basis. We establish combinatorial conditions on subsets S and T of Fourier basis elements under which nonnegative functions with Fourier support S are sums of squares of functions with Fourier support T. Our combinatorial condition involves constructing a chordal cover of a graph related to G and S (the Cayley graph Cay($\hat{G}$,S)) with maximal cliques related to T. Our result relies on two main ingredients: the decomposition of sparse positive semidefinite matrices with a chordal sparsity pattern, as well as a simple but key observation exploiting the structure of the Fourier basis elements of G. We apply our general result to two examples. First, in the case where $G={\mathbb{Z}}_2^n$, by constructing a particular chordal cover of the half-cube graph, we prove that any nonnegative quadratic form in n binary variables is a sum of squares of functions of degree at most $\lceil n/2\rceil$, establishing a conjecture of Laurent. Second, we consider nonnegative functions of degree d on ${\mathbb{Z}}_N$ (when d divides N). By constructing a particular chordal cover of the d'th power of the N-cycle, we prove that any such function is a sum of squares of functions with at most $3d\log (N/d)$ nonzero Fourier coefficients. Dually this shows that a certain cyclic polytope in ${\mathbb{R}}^{2d}$ with N vertices can be expressed as a projection of a section of the cone of psd matrices of size $3d\log (N/d)$. Putting $N=d^2$ gives a family of polytopes $P_d\subset {\mathbb{R}}^{2d}$ with LP extension complexity ${\text{xc}}_{LP}(P_d)=\Omega (d^2)$ and SDP extension complexity ${\text{xc}}_{PSD}(P_d)=O(d\log (d))$. To the best of our knowledge, this is the first explicit family of polytopes in increasing dimensions where ${\text{xc}}_{PSD}(P_d)=o({\text{xc}}_{LP}(P_d))$.

34 pages

References in corpus (3)

• Positive semidefinite rank
• Equivariant semidefinite lifts and sum-of-squares hierarchies
• Small Extended Formulations for Cyclic Polytopes

Cited by in corpus (4)

• Lifting for Simplicity: Concise Descriptions of Convex Sets
• A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian
• A Gramian Description of the Degree 4 Generalized Elliptope
• Equivariant semidefinite lifts of regular polygons