Sparse sums of squares on finite abelian groups and improved semidefinite lifts

作者：Fawzi Hamza^*; Saunderson James; Parrilo Pablo A

来源：Mathematical Programming, 2016, 160(1-2): 149-191.

DOI：10.1007/s10107-015-0977-z

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 and of Fourier basis elements under which nonnegative functions with Fourier support are sums of squares of functions with Fourier support . Our combinatorial condition involves constructing a chordal cover of a graph related to G and (the Cayley graph ) with maximal cliques related to . 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 (the characters of G). We apply our general result to two examples. First, in the case where , 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 , establishing a conjecture of Laurent. Second, we consider nonnegative functions of degree d on (when d divides N). By constructing a particular chordal cover of the dth power of the N-cycle, we prove that any such function is a sum of squares of functions with at most nonzero Fourier coefficients. Dually this shows that a certain cyclic polytope in with N vertices can be expressed as a projection of a section of the cone of positive semidefinite matrices of size . Putting gives a family of polytopes in with linear programming extension complexity and semidefinite programming extension complexity . To the best of our knowledge, this is the first explicit family of polytopes in increasing dimensions where , where and are respectively the SDP and LP extension complexity.

• 出版日期2016-11