Sparse sums of squares on finite abelian groups and improved semidefinite lifts
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2016
|
| Online Access: | http://hdl.handle.net/1721.1/104800 https://orcid.org/0000-0001-6026-4102 https://orcid.org/0000-0003-1132-8477 |
| _version_ | 1826191459487842304 |
|---|---|
| author | Fawzi, Hamza Saunderson, James F Parrilo, Pablo A |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Fawzi, Hamza Saunderson, James F Parrilo, Pablo A |
| author_sort | Fawzi, Hamza |
| collection | MIT |
| description | 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(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 (the characters of G). We apply our general result to two examples. First, in the case where G=Zn2, 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 ⌈n/2⌉, establishing a conjecture of Laurent. Second, we consider nonnegative functions of degree d on ZN (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 3dlog(N/d) nonzero Fourier coefficients. Dually this shows that a certain cyclic polytope in R2d with N vertices can be expressed as a projection of a section of the cone of positive semidefinite matrices of size 3dlog(N/d). Putting N=d2 gives a family of polytopes in R2d with linear programming extension complexity Ω(d2) and semidefinite programming extension complexity O(dlog(d)). To the best of our knowledge, this is the first explicit family of polytopes (Pd) in increasing dimensions where xcPSD(Pd)=o(xcLP(Pd)), where xcPSD and xcLP are respectively the SDP and LP extension complexity. |
| first_indexed | 2024-09-23T08:56:11Z |
| format | Article |
| id | mit-1721.1/104800 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:56:11Z |
| publishDate | 2016 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1048002022-09-26T09:19:52Z Sparse sums of squares on finite abelian groups and improved semidefinite lifts Fawzi, Hamza Saunderson, James F Parrilo, Pablo A Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Fawzi, Hamza Saunderson, James F Parrilo, Pablo A 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(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 (the characters of G). We apply our general result to two examples. First, in the case where G=Zn2, 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 ⌈n/2⌉, establishing a conjecture of Laurent. Second, we consider nonnegative functions of degree d on ZN (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 3dlog(N/d) nonzero Fourier coefficients. Dually this shows that a certain cyclic polytope in R2d with N vertices can be expressed as a projection of a section of the cone of positive semidefinite matrices of size 3dlog(N/d). Putting N=d2 gives a family of polytopes in R2d with linear programming extension complexity Ω(d2) and semidefinite programming extension complexity O(dlog(d)). To the best of our knowledge, this is the first explicit family of polytopes (Pd) in increasing dimensions where xcPSD(Pd)=o(xcLP(Pd)), where xcPSD and xcLP are respectively the SDP and LP extension complexity. United States. Air Force Office of Scientific Research (AFOSR FA9550-11-1-0305) United States. Air Force Office of Scientific Research (AFOSR FA9550-12-1-0287) 2016-10-13T18:48:42Z 2017-03-01T16:14:49Z 2016-01 2015-04 2016-10-09T03:26:27Z Article http://purl.org/eprint/type/JournalArticle 0025-5610 1436-4646 http://hdl.handle.net/1721.1/104800 Fawzi, Hamza, James Saunderson, and Pablo A. Parrilo. “Sparse Sums of Squares on Finite Abelian Groups and Improved Semidefinite Lifts.” Mathematical Programming 160, no. 1–2 (January 27, 2016): 149–191. https://orcid.org/0000-0001-6026-4102 https://orcid.org/0000-0003-1132-8477 en http://dx.doi.org/10.1007/s10107-015-0977-z Mathematical Programming Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Fawzi, Hamza Saunderson, James F Parrilo, Pablo A Sparse sums of squares on finite abelian groups and improved semidefinite lifts |
| title | Sparse sums of squares on finite abelian groups and improved semidefinite lifts |
| title_full | Sparse sums of squares on finite abelian groups and improved semidefinite lifts |
| title_fullStr | Sparse sums of squares on finite abelian groups and improved semidefinite lifts |
| title_full_unstemmed | Sparse sums of squares on finite abelian groups and improved semidefinite lifts |
| title_short | Sparse sums of squares on finite abelian groups and improved semidefinite lifts |
| title_sort | sparse sums of squares on finite abelian groups and improved semidefinite lifts |
| url | http://hdl.handle.net/1721.1/104800 https://orcid.org/0000-0001-6026-4102 https://orcid.org/0000-0003-1132-8477 |
| work_keys_str_mv | AT fawzihamza sparsesumsofsquaresonfiniteabeliangroupsandimprovedsemidefinitelifts AT saundersonjamesf sparsesumsofsquaresonfiniteabeliangroupsandimprovedsemidefinitelifts AT parrilopabloa sparsesumsofsquaresonfiniteabeliangroupsandimprovedsemidefinitelifts |