In these previous posts, we explored whether the cut polytope can be expressed as the linear projection of a polytope with a small number of facets (i.e., whether it has a small linear programming extended formulation).
For many cut problems, semi-definite programs (SDPs) are able to achieve better approximation ratios than LPs. The most famous example is the Goemans-Williamson -approximation for MAX-CUT. The techniques of the previous posts (see the full paper for details) are able to show that no polynomial-size LP can achieve better than factor .
1.1. Spectrahedral lifts
The feasible regions of LPs are polyhedra. Up to linear isomorphism, every polyhedron can be represented as where is the positive orthant and is an affine subspace.
In this context, it makes sense to study any cones that can be optimized over efficiently. A prominent example is the positive semi-definite cone. Let us define as the set of real, symmetric matrices with non-negative eigenvalues. A spectrahedron is the intersection with an affine subspace . The value is referred to as the dimension of the spectrahedron.
In analogy with the parameter we defined for polyhedral lifts, let us define for a polytope to be the minimal dimension of a spectrahedron that linearly projects to . It is an exercise to show that for every polytope . In other words, spectahedral lifts are at least as powerful as polyhedral lifts in this model.
In fact, they are strictly more powerful. Certainly there are many examples of this in the setting of approximation (like the Goemans-Williamson SDP mentioned earlier), but there are also recent gaps between and for polytopes; see the work of Fawzi, Saunderson, and Parrilo.
Nevertheless, we are recently capable of proving strong lower bounds on the dimension of such lifts. Let us consider the cut polytope as in previous posts.
Theorem 1 (L-Raghavendra-Steurer 2015) There is a constant such that for every , one has .
Our goal in this post and the next is to explain the proof of this theorem and how quantum entropy maximization plays a key role.
1.2. PSD rank and factorizations
Just as in the setting of polyhedra, there is a notion of “factorization through a cone” that characterizes the parameter . Let be a non-negative matrix. One defines the psd rank of as the quantity
The following theorem was independently proved by Fiorini, Massar, Pokutta, Tiwary, and de Wolf and Gouveia, Parrilo, and Thomas. The proof is a direct analog of Yannakakis’ proof for non-negative rank.
Theorem 2 For every polytope , it holds that for any slack matrix of .
Recall the class of non-negative quadratic multi-linear functions that are positive on and the matrix given by
We saw previously that is a submatrix of some slack matrix of . Thus our goal is to prove a lower bound on .
1.3. Sum-of-squares certificates
Just as in the setting of non-negative matrix factorization, we can think of a low psd rank factorization of as a small set of “axioms” that can prove the non-negativity of every function in . But now our proof system is considerably more powerful.
For a subspace of functions , let us define the cone
This is the cone of squares of functions in . We will think of as a set of axioms of size that is able to assert non-negativity of every by writing
for some .
Fix a subspace and let . Fix also a basis for .
Define by setting . Note that is PSD for every because where .
We can write every as . Defining by , we see that
Now every can be written as for some and . Therefore if we define (which is a positive sum of PSD matrices), we arrive at the representation
In conclusion, if , then .
By a “purification” argument, one can also conclude .
1.4. The canonical axioms
And just as -juntas were the canonical axioms for our NMF proof system, there is a similar canonical family in the SDP setting: Let be the subspace of all degree- multi-linear polynomials on . We have
For a function , one defines
For a function , one defines
(One could debate whether the definition of sum-of-squares degree should have or . The most convincing arguments suggest that we should use membership in the cone of squares over so that the sos-degree will be at least the real-degree of the function.)
On the other hand, our choice has the following nice property.
Lemma 3 For every , we have .
Proof: If is a non-negative -junta, then is also a non-negative -junta. It is elementary to see that every -junta is polynomial of degree at most , thus is the square of a polynomial of degree at most .
1.5. The canonical tests
As with junta-degree, there is a simple characterization of sos-degree in terms of separating functionals. Say that a functional is degree- pseudo-positive if
whenever satisfies (and by here, we mean degree as a multi-linear polynomial on ).
Again, since is a closed convex set, there is precisely one way to show non-membership there. The following characterization is elementary.
Lemma 4 For every , it holds that if and only if there is a degree- pseudo-positive functional such that .
1.6. The connection to psd rank
Following the analogy with non-negative rank, we have two objectives left: (1) to exhibit a function with large, and (ii) to give a connection between the sum-of-squares degree of and the psd rank of an associated matrix.
Notice that the function we used for junta-degree has , making it a poor candidate. Fortunately, Grigoriev has shown that the knapsack polynomial has large sos-degree.
Theorem 5 For every odd , the function
Observe that this is non-negative over (because is odd), but it is manifestly not non-negative on .
Finally, we recall the submatrices of defined as follows. Fix some integer and a function . Then is given by
In the next post, we discuss the proof of the following theorem.
Theorem 6 (L-Raghavendra-Steurer 2015) For every and , there exists a constant such that the following holds. For every ,
Note that the upper bound is from (1) and the non-trivial content is contained in the lower bound. As before, in conjunction with Theorem 5, this shows that cannot be bounded by any polynomial in and thus the same holds for .