What is a "level-r pseudo expectation functional"?

Question

In the context of the SOS hierarchy papers, it seems that a "level-r psuedo expectation functional" is the same as an operator taking expectations of functions just that this one has the restriction that expectation of a square of a function is guaranteed to be zero only when the function is a polynomial of degree $\leq \frac{r}{2}$

• Is the above right?

• So the polynomials on which one would take the "level-r pseudo expectation functional" are what are to be called "level-r fictitious random variable" ?

• Conventionally in optimization questions one would say something like "maximize $P_0$ given that $P_i^2=0$ for $i =1,2,..,m$" but the ``r-round SOS SDP relaxation" of this same question would be to choose a "level-r pseudo expectation functional" say $\tilde{E}$ and say "maximize $\tilde{E}[P_0]$ given that $\tilde{E}[P_i^2]=0$ for $i =1,2,..,m$ for $deg(P_i) \leq \frac{r}{2}$"

Is the above right? And if so then how is a specific $\tilde{E}$ chosen to do the relaxation?

Answer 1

The degree $r$ pseudo-expectation operator operates on polynomials of at most degree $r$. Since the pseudo-expectation operator is positive semidefinite, we're guaranteed that the square of a polynomial (or sum of squares of polynomials) always has nonnegative pseudo-expectation.

Also, if we have a system of polynomial equations $\{p_i = 0\}$ of degree at most $r/2$, then we can construct the pseudo-expectation operator to be such that the pseudo-expectation $\tilde{\mathbb{E}}[p_i q] = 0$ for all polynomials $q$ of sufficiently small degree.

The intuition should be that if $\{p_i=0\}$ has a feasible solution, then $\mathbb{E}[ p_i(x) ] = 0$ where $x$ is a random feasible solution to $\{p_i = 0\}$ and $\mathbb{E}$ is the "actual" expectation operator.

But of course, it is not possible for us to directly sample this distribution. Instead we play a sort of game where we assume that we can evaluate various expectations of polynomials $\mathbb{E}[p]$ (that is, moments) of this distribution over feasible solutions, and 'combine' them together to get a feasible solution.

But of course, we don't really have those moments, either, because again it's too hard to sample the distribution. So we instead use the SoS algorithm to find a pseudo-distribution and pseudo-expectation operator that we can evaluate to get pseudo-moments $\tilde{\mathbb{E}}[p]$, and feed the pseudo-moments to the same 'combiner' algorithm as if they were actual moments, and sometimes we get an answer out that's actually not half bad.

Edit: It is better to consider the sum of squares SDP as optimizing a particular pseudo-expectation; for example, in Goemans-Williamson, we maximize $\tilde{\mathbb{E}}[ \langle x, Lx \rangle]$ where $L$ is the Laplacian and this corresponds to maximizing the value of our cut.